prove by counting two ways:

enter image description here

I though to prove the right hand side I would say: Let n represent a number of boys and m a number of girls. We want to choose a group of n from boys and girls. But for the left hand side I want to keep the variables m and n girls and boys. But I don't know what k will be. Suggestions?

  • 5
    $\begingroup$ Hint: replace $\binom nk$ by $\binom n{n-k}$. $\endgroup$ – Marc van Leeuwen Feb 15 '14 at 12:57
  • 2
    $\begingroup$ $(1+x)^m(1+x)^n=(1+x)^{m+n}$ $\endgroup$ – Lucian Feb 15 '14 at 13:26

Suppose $n \leq m $.

Then if you want to choose $n$ people, you can choose $k$ boys in $\binom{n}{k}$ ways and $n-k$ girls in $\binom{m}{n-k}$ ways , for $k \in \{0,1, \dots n\}$.

So we have $$\sum_{k = 0}^{n} \binom{n}{k} \binom{m}{n-k} = \binom{n+m}{n}$$


If you are choosing $k$ girls, then exactly $k$ of the boys will not be chosen (since you are choosing as many children as there are boys).


Your Answer

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

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