Yesterday, I was made aware of an elementary combinatorics problem, and the solution was surprisingly clever (at least it is to me, though I am not an expert in the area).
Suppose that a philanthropist decides to give a total of ten dollars in one-dollar bills to 3 people. How many ways can we distribute the money, assuming that we don’t have to do so evenly?
Take 13 one-dollar bills and lay them out in front of you.
[] [] [] [] [] [] [] [] [] [] [] [] []
Between these, there are 12 gaps where you could draw lines, and two of these lines will give one possible outcome. Suppose that we’ve partitioned them.
[] [] [] [] [] | [] [] [] [] [] [] [] | []
Now, we give out the bills to these three people, but we keep one bill in each partition so as to retain those 3 extra dollars. Thus, in the partition above, Person 1 gets 4, Person 2 gets 6, and Person 3 feels left out having only a single dollar in his partition, which the philanthropist then picks up and keeps.
How many ways can we do this? Between our 13 dollar bills, we had 12 gaps. To create 3 portions, we had to draw lines in 2 of those gaps. Thus, there are $\binom{12}{2} = 66$ ways to do so.
Now, let’s do this in general, where we distribute $n$ items among $k$ recipients.
Theorem. Let $n,k\in\mathbb{Z}$ with $n\geq0,k\geq1$. The number of ways to distribute $n$ (indistinguishable) items among $k$ (distinguishable) recipients is $\displaystyle{\binom{n+k-1}{k-1}}$.
Proof. If we list our items side-by-side, we can specify a distributions by simply drawing lines between adjacent elements until $k$ portions are made. To do this, we need $k-1$ of these lines. Now, we must count the number of possible positions for these lines.
Each space adjacent to an item (including the left of the first item and the right of the last) may have up to $k-1$ lines until they’re all taken, where adjacent lines specify empty portions. Since there are $n$ items, there are $n+k-1$ positions for these lines.
Therefore, the problem is the same as finding the number of ways to choose $k-1$ of these positions, out of the possible $n+k-1$ positions, and so we have that the number of ways to distribute $n$ items among $k$ recipients is $\displaystyle{\binom{n+k-1}{k-1}}$. QED
In this proof, we alleviated the need to add $k$ items by simply allowing adjacent lines to create empty portions.
In doing this, however, I wondered how the problem may change if our philanthropist decided to keep some of the initial money. How many ways can we give 10 one-dollar bills to 3 people, while allowing the philanthropist to keep some of it?
This means that we’re allowing for only 9 of the 10 dollar bills to be given away, or even 0 of them, if our philanthropist has decided not to go through with it. The obvious answer is to add up the number of ways in all of the possible scenarios. Therefore, the answer would be (in the general case) $$\sum_{\ell=0}^{n} \binom{\ell+k-1}{k-1}.$$
An equivalent formulation of this problem is to treat the philanthropist as another recipient, as whatever is kept can be treated as being redistributed back to them. Thus, given that this now means that there are $k+1$ recipients, the answer is also $\binom{n+k}{k}.$ Since equivalent formulations to the same problem should have the same answer, we’ve proven a corollary to our theorem, which is the following identity:
Corollary. Let $n,k\in\mathbb{Z}$ with $n\geq0,k\geq1$. Then, $$\binom{n+k}{k}=\sum_{\ell=0}^{n} \binom{\ell+k-1}{k-1}.$$
If our philanthropist says they may decide to keep some of the 10 one-dollar bills, then the number of ways that they could be distributed is $$\binom{13}{3}=286=$$
$$1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 + 55 + 66=$$
$$\binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} + \binom{6}{2} + \binom{7}{2} + \binom{8}{2} + \binom{9}{2} + \binom{10}{2} + \binom{11}{2} + \binom{12}{2}$$