1
$\begingroup$

Argue that

$\binom{n}{n_1,n_2,...,n_r} = \binom{n-1}{n_1-1,n_2,...,n_r} + \binom{n-1}{n_1,n_2-1,...,n_r}+...+\binom{n-1}{n_1,n_2,...,n_r-1} $

Each term on the right hand side is the number of ways of dividing $n-1$ distinct objects into $r$ distinct groups. I cant really make a start on this.

I have thought about it in terms of apples to try and get a grasp of the problem, if i were to have 10 apples labeled 1- 10 and 3 groups of size 2,3,5. Then the math works out.

If I have $n$ apples labeled $1$ through $n$, if I choose the first(labelled 1) apple and fix it to the 1st group then divide the remaining $n-1$ apples into the $r$ groups, there are $\binom{n-1}{n_1-1,n_2,...,n_r}$ ways to do this. If I repeat this process with apple 2 and place the apple in group 2 instead, we obtain $\binom{n-1}{n_1,n_2-1,...,n_r}$ continuing in this fashion when we fix the $r$th apple to the $r$th group and count the number of ways of distributing the remaining $n-1$ apples to the $r$ groups we get $\binom{n-1}{n_1,n_2,...,n_r-1}$. Summing the terms on the right will then give us the number of ways of dividing the $n$ distinct apples into $r$ distinct groups.

$\endgroup$
0
$\begingroup$

Your argument using apples is very close, maybe only a bit awkwardly written. We give a combinatorical argument of equality, showing the the rhs and lhs count the same thing.

Now, the lhs is easy: it counts the number of ways to partition $n$ apples into $r$ groups with sizes $n_1, n_2, \ldots, n_r$.

We want to show that the rhs counts this as well. Let's pick a fixed apple. The essesce of the proof is noting that:

(the number of ways to partition apples into $r$ groups of specified sizes) = (the number of ways we can partition apples into $r$ groups of specified sizes if the fixed apple is in the first group) + (the number of ways we can partition apples into $r$ groups of specified sizes if the fixed apple is in the second group) + ... + (the number of ways we can partition apples into $r$ groups of specified sizes if the fixed apple is in the last group)

This options are disjoint, so we can freely sum the number of cases in each option. Now, lets count the number of ways in each of the options.

If we put it in the first group, then to get partitions into $r$ groups with sizes $n_1, n_2, \ldots, n_r$, we need to arrange remaining $n-1$ apples into groups of sizes $n_1-1$, $n_2$, ..., $n_r$, as we already have one apple in the first group. We can do this in $\binom{n-1}{n_1-1, n_2, \ldots, n_r}$ many ways. Similary, we can put our apple in second group, which yields $\binom{n-1}{n_1, n_2-1, \ldots, n_r}$ ways, and so forth until the $r$-th group.

Rewriting equation in text above into numbers, we get the desired equality.

PS: The case by case distinction intuitivnely reminds me of the law of total probabilities, it it helps you to think about it that way.

$\endgroup$
  • 1
    $\begingroup$ I see how my answer is awkwardly written, I was fixing a different apple each time. Thanks :) +1 and accepted. $\endgroup$ – user197848 Jul 26 '15 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy