What is the intuition behind
$$ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} $$
? I can't grasp why picking a group of $k$ out of $n$ bijects to first picking a group of $k-1$ out of $n-1$ and then a group of $k$ out of $n-1$.
$\begingroup$
$\endgroup$
8
asked May 15, 2013 at 16:47
-
$\begingroup$ math.stackexchange.com/questions/86093/… $\endgroup$– lab bhattacharjeeCommented May 15, 2013 at 16:49
-
$\begingroup$ @labbhattacharjee Why link to a question that has been closed as duplicate when mentioning that a question is a duplicate? $\endgroup$– Tobias KildetoftCommented May 15, 2013 at 16:52
-
1$\begingroup$ @TobiasKildetoft, could have supplied the one not closed as duplicate, but the closed one also has some additional solutions as well $\endgroup$– lab bhattacharjeeCommented May 15, 2013 at 16:55
-
$\begingroup$ en.wikipedia.org/wiki/Pascal%27s_triangle may be a useful visual aid as consider any spot in the triangle and notice that unless it is a 1 on the side, it is the sum of the two values above it. $\endgroup$– JB KingCommented May 15, 2013 at 18:25
-
1$\begingroup$ It is not "first picking... and then..." but "either picking... or...". Remember "or" (if exclusive) leads to "$+$" while "and" leads to "$\times$". $\endgroup$– Marc van LeeuwenCommented May 16, 2013 at 9:14
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
4
We have a group of $n$ people, one of whom is John. We want to pick a committee of $k$ people. By definition this can be done in $\binom{n}{k}$ ways.
There are $\binom{n-1}{k}$ committees of $k$ that don't include John, for we can choose any $k$ of the people other than John. And there are $\binom{n-1}{k-1}$ committees of $k$ that do include John, for we can choose any $k-1$ people to join John.
Note that automatically a committee that doesn't include John is different from a committee that includes John. So we have divided the $\binom{n}{k}$ possible committees into two groups, one of which has $\binom{n-1}{k}$ elements, and the other of which has $\binom{n-1}{k-1}$ elements.
answered May 15, 2013 at 16:50
-
6$\begingroup$ Great, now how do we solve the problem if nobody on the committee is named John? ;) $\endgroup$ Commented May 15, 2013 at 17:01
-
6$\begingroup$ It will take a while, but we can apply for a legal change of name, and then we can use the above solution. $\endgroup$ Commented May 15, 2013 at 17:03
-
3$\begingroup$ If there are two people named John, then we're really screwed. $\endgroup$ Commented May 15, 2013 at 17:17
-
1$\begingroup$ @MarkAdler: Implicitly, the Change of Name Lemma above solves that problem. $\endgroup$ Commented May 15, 2013 at 17:24
$\begingroup$
$\endgroup$
1
You don't pick a group of $k-1$ out of $n-1$ and a group of $k$ out of $n-1$; this would correspond to multiplication. You should do one or the other.
The key is to pick one of your $n$ objects as being special. Then any collection of $k$ objects from the $n$ either consists of $k-1$ objects from the $n-1$ non-special objects, plus the special one, or it consists entirely of $k$ non-special objects. There are $\binom{n-1}{k}$ collections of $k$ non-special objects, and $\binom{n-1}{k-1}$ collections of $k$ objects including the special one.
-
$\begingroup$ This answer is basically a wordier version of André's, who was first, but I decided to post it anyway for the first paragraph. $\endgroup$– mdpCommented May 15, 2013 at 16:52