1
$\begingroup$

Let $p_k(n)$ be a number of ways to express $n$ as a sum of $k$ positive integers. For example $p_2(3)=1$.

Problem 1. Prove that following recurrences are correct:

$p_k(n)=p_{k-1}(n-1)+p_k(n-k)$

$p_k(n)=p_k(n-k)+p_{k-1}(n-k) + ... + p_1(n-k)$

Problem 2. Find $p_2(n)$ and $p_3(n)$.

Unfortunately I was always weak in showing recurrences and I have no idea for 1. I tried to use Ferrers diagrams to see sth but I haven't seen anything. For 2 it is easy to observe that $p_2(n)=\lfloor n/2 \rfloor$ and using first recurrence, that I failed to prove, I got $\displaystyle p_3(n)=\sum_{k=0}^{\lceil n/2 \rceil-1} \left\lfloor\frac{n-3k-1}{2}\right\rfloor$ but I don't know if it's possible to simplify this sum. Maybe some combinatorial interpretation, with Ferrers diagrams for example, will lead to more explicit form for $p_3(n)$?

1 Answers 1

2

For Problem 1:

a) Either you have a part that's $1$, then the remaining parts can be any partition of $n-1$ into $k-1$ parts, or you don't, then you can subtract $1$ from all $k$ parts and are left with a partition of $n-k$ into $k$ parts.

b) Subtract $1$ from every part; then you have $n-k$ left, in anything from $1$ to $k$ parts.

  • 0
    @Marc: True -- so we should add a term $p_0(n-k)$ to the sum, which would be $0$ for $k\ne n$ and $1$ for $k=n$?2012-09-02