12
$\begingroup$

Why, conceptually, is it that $$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}?$$ I know how to prove that this is true, but I don't understand conceptually why it makes sense.

$\endgroup$
7
  • 2
    $\begingroup$ This question have been asked here many times. Neither of the answer to those questions was satisfactory to you? math.stackexchange.com/questions/86093/…, math.stackexchange.com/questions/392595/…, math.stackexchange.com/questions/20475/… and many other questions list there among linked questions. $\endgroup$ – Martin Sleziak Jan 4 '14 at 8:49
  • 2
    $\begingroup$ Those posts were mostly discussing proofs for why this equality is true. After reading them, I still didn't feel that I understood the intuition behind it. I'm sorry if this question seems repetitive. $\endgroup$ – okarin Jan 4 '14 at 8:51
  • 2
    $\begingroup$ But several of those posts have as one of the answers the same argument as in the answer you have accepted here... $\endgroup$ – Martin Sleziak Jan 4 '14 at 8:52
  • 3
    $\begingroup$ The phrasing of the answer I accepted makes more sense to me than those. It is, however, possible that I might have missed an answer. $\endgroup$ – okarin Jan 4 '14 at 8:53
  • 2
    $\begingroup$ At this point, I have gotten the answer that I was looking for, so whether or not you close does not concern me. $\endgroup$ – okarin Jan 4 '14 at 10:11
7
$\begingroup$

Sure. You're dividing into 2 cases. On the one hand you're saying I'm stuck choosing this element over here. So now I have r-1 more choices to make out of n-1 things. In the other case you're refusing that element. Now you've eliminated a choice, but still must pick r elements. These two cases are exhaustive and exclusive.

$\endgroup$
15
$\begingroup$

Because the number of ways that we can make a team of a certain size is equal to the number of ways that we can make a team of the same size without Fred, plus the number of ways we can make a team of size one smaller, plus Fred.

$\endgroup$
3
  • 3
    $\begingroup$ dang. A deluge of answers just fell. $\endgroup$ – Andrew Marshall Jan 4 '14 at 6:40
  • $\begingroup$ @Slade: Please, can you explain this similar identity also. Thank you. $\endgroup$ – Bumblebee Mar 7 '15 at 7:18
  • 1
    $\begingroup$ @Nilan The number of ways we can pick a team of $r$ people, and then name one of them Bob, equals the number of ways we can name one person Bob, and then pick a team of $r-1$ other people. This generalizes to the case of more than one Bob. $\endgroup$ – Slade Mar 8 '15 at 3:23
8
$\begingroup$

The number of the combination that we choose $r$ people from $n$ people is the sum of the number of the combination that a person named $A$ is included and the number of the combination that $A$ is not included.

$\endgroup$
4
$\begingroup$

Another simple way to look at it is Pascal's triangle. This is simply a formulation of the rule that governs the triangle -- an entry is the sum of the two entries above it. The $i$-th entry in the $n$-th row is the sum of the $i-1$-th entry in the $n-1$-th row and the $i$-th entry in the $n-1$-th row. Hence, $$\binom{n-1}{i-1}+\binom{n-1}{i}=\binom{n}{i}$$

$\endgroup$
1
  • $\begingroup$ This presumes that Pascal's triangle means something for binomial coefficients... $\endgroup$ – Ryan Reich Jan 4 '14 at 7:08
2
$\begingroup$

Consider picking $r$ objects out of a set of $n$ of them. Pick a particular object $O$. Either your set has $O$, or it doesn't. There are $\binom{n - 1}{r - 1}$ sets with $O$, and $\binom{n - 1}{r}$ sets without it. (Do you see why those are true?) So together, there are $\binom{n - 1}{r - 1} + \binom{n - 1}{r}$ sets of size $r$.

$\endgroup$
1
$\begingroup$

The number of ways of choosing $r$ items from $n$ distinct items is the same as

  • choosing $r-1$ items from the first $n-1$ items (and add to the last item), plus
  • choosing $r$ items from the first $n-1$ items (and not choosing the last item)
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.