partitions and their generating functions and Partitions of n

Question

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k parts. p(4,2)= 2, because (2+2) , (1+3).

i want to find a recurrence relation for p(n,k)?

i read some note about Ferrer diagram, but i couldn't find such recurrence.

any hint or idea?

Answer 1

Hint: the partition either has a 1 for one of its parts, or it doesn't.

Answer: If one of the parts is 1, then the remaining $k-1$ parts partition $n-1$, so there are $p(n-1,k-1)$ partitions where at least one part is 1. Otherwise, every part is at least 2: removing one from each part leaves a partition of $n-k$ into $k$ parts, so there are $p(n-k,k)$ of these partitions. These are all possible cases, proving the recurrence $$ p(n,k) = p(n-1,k-1) + p(n-k,k) $$

Answer 2

I think it is actually slightly easier to compute $p(n,k)$ as the number of partitions of $n$ with $k$ as largest part; that this is the same number as in the question follows from the transposition of Ferrers diagrams.

Now removing the part $k$, we are left with a partition of $n-k$ into parts at most equal to $k$; define $p'$ by the relation $p(n,k)=p'(n-k,k)$. Now a partition with parts at most equal to $k$ either has a part $k$, or is a partition with parts at most equal to $k-1$: $$ p′(m,k)=p(m,k)+p′(m,k-1) $$ The case $k=0$ is easy to handle. From this you can work out a recursion for $p(n,k)$.