Give combinatoric argument for partition counting: $P(n, k) = P(n -1, k -1) + P(n-k,k)$

Question

Suppose you have $n$ identical pieces. You want to split them in $k$ groups. (each group must have $> 0$ pieces)

First, I was ask to answer the basic cases $1 \le k \le n \le 5$

For examble, $$P(4,1) = 1$$ $$P(5,1) = 1$$ $$P(4,2) = 2$$ $$P(5,3) = 2$$

Now I want to prove those 3 with combinatoric arguments.

1. $P(n,k) = 0 \text{ if } n < k$
2. $P(n,n) = P(n,1) = 1$
3. $P(n, k) = P(n -1, k -1) + P(n-k,k)$

For the first one, my answer is : The function must be surjective. However, $|n| < |k|$, which cannot be surjective.

But I'm pretty sure this is not a combinatoric argument.

Answer 1

1. You don’t really have functions, since the objects, which ought to be the elements of the domain, are indistinguishable. However, you can use the same basic idea: if $n<k$, there is no way to make each group non-empty.

2. $P(n,n)$ is the number of ways to put the $n$ objects into $n$ non-empty groups. Clearly there’s only one way to do this: put one object into each group. (Since the objects are indistinguishable, there’s only one way to do this.) $P(n,1)$ is the number of ways to put the $n$ objects into a single group, and that’s clearly also just $1$.

3. $P(n, k) = P(n -1, k -1) + P(n-k,k)$ is the interesting one. HINT: There are two kinds of arrangements of $n$ objects in $k$ groups: those in which some group has only one object, and those in which every group has at least two objects. There are $P(n-1,k-1)$ arrangements of the first type; can you see why? And there are $P(n-k,k)$ of the second type; again, can you see why? (In both cases think about throwing away one or more objects.)

Answer 2

So $P(n,k)$ counts the partitions of the number $n$ into $k$ (nonzero) parts, where the order of the parts is ignored (this is implied by the term "partition of $n$").

Since each part must be at least $1$, having $k$ parts makes their sum at least $k$, which cannot be $n$ if $k>n$; this is your first point.

If you want to have just one part, you must take $n$ as only part, and if you want exactly $n$ parts all parts must be equal to $1$ (if not the sum of parts would again be too large); this gives $P(n,1)=1$ and $P(n,n)=1$, respectively. (Note that $P(0,1)=0$, so the former equation (and the argument for it), fails for $n=0$; I assume you are ignoring that case, but it is good to pay attention to limiting cases when doing recurrence).

Finally if both $n$ and $k$ are greater than $1$, you can relate to $P(n-1,k-1)$ by observing that you can always add a single part $1$ to a partition of $n-1$ into $k-1$ parts to obtain a partition of $n$ into $k$ parts; moreover all partitions so constructed are different. But they do not produce all partitions of $n$ into $k$ parts, since they always produce at least one part $1$; what is missing is those partitions of $n$ into $k$ parts that do not contain any part equal to $1$. The idea to account for those partition is to slice off a unit from each part (decrease each part by $1$), which decreases the sum by $k$, and leaves the number of parts unchanged (because all were at least $2$ originally). So you get a partition of $n-k$ into $k$ parts. Now it remains to convince yourself that inversely every contribution to $P(n-k,k)$ gives a contribution to $P(n,k)$; this is easy.