I'm trying to prove this combinatorially. $$k\binom{n}{k} = n\binom{n-1}{k-1}$$ I know the first step is to relate a question to the equation. My question was if you have $n$ friends how many ways can you choose $k$ of them. I know this isn't correct because that would be the question if the left side wasn't being multiplied by k. Can anyone help me figure out what multiplying ${n \choose k}$ by $k$ means?
Asked
Active
Viewed 402 times
3
-
1See http://math.stackexchange.com/questions/299598/combinatorial-argument-for-the-identity-k-binomnk-n-binomn-1k-1?rq=1 – Jean-Claude Arbaut May 15 '14 at 07:17
-
Algebraic approach can be found here (and probably in several other posts): http://math.stackexchange.com/questions/743261/prove-k-binom-nk-n-binomk-1-n-1-algebraically – Martin Sleziak May 15 '14 at 08:22
1 Answers
10
The standard example is that you have a group of $n$ people, and want to pick a committee of $k$, including a designated committee Chair. We count the number of ways to do this in two ways.
(a) You can pick $k$ people, and then pick one of these to be Chair. This can be done in $\binom{n}{k}\cdot k$ ways.
(b) You can pick a Chair, and pick $k-1$ people to join her. This can be done in $n\binom{n-1}{k-1}$ ways.
Remark: A less bureaucratic example would be nice. You have $n$ friends and a large van, and want to pick $k$ friends to go drinking, with one of them the designated driver.
André Nicolas
- 507,029