0
$\begingroup$

Without algebraically manipulating this following equality (i.e. reducing down to $n - 1 +r\choose n-1 $ etc. ), what is a combinatorial proof for this following equation?:

$$ \left(\!\!{n \choose r}\!\!\right) = \left(\!\!{n \choose {r-1}}\!\!\right) + \left(\!\!{ {n - 1} \choose r }\!\!\right) $$

I can easily understand the LHS: we're placing r indistinguishable items into n distinguishable bins. Hence, n multichoose r.

However, as for the RHS, I'm having trouble understanding the disjoint cases here that allows for the use of The Sum Rule.

$\endgroup$
  • $\begingroup$ Your formula is false: the first term in the r.h.s. should be $\dbinom{n-1}{r-1}$. $\endgroup$ – Bernard Feb 12 '18 at 19:27
2
$\begingroup$

Consider the two cases, which are based on what you can do with bin $n$:

  • either you decide to use bin $n$, so at least one item gets placed in it, after which you have to place $r - 1$ items to $n$ bins, or
  • bin $n$ is not used at all, which means you have to place $r$ indistinguishable items to $n - 1$ bins

Therefore,

$$ \def\multiset#1#2{{\left(\kern-.3em\left(\genfrac{}{}{0pt}{}{#1}{#2}\right)\kern-.3em\right)}} \multiset{n}{r} = \multiset{n}{r - 1} + \multiset{n - 1}{r} $$

$\endgroup$
1
$\begingroup$

Left hand side: total number of multisets with size r on an n-element set.

Right hand side: Pick a certain element $x$ of the $n$-element set. Break the set of all multisets into 2 types: those containing an instance of $x$ and those not containing an instance of $x$.

$\endgroup$
0
$\begingroup$

We have that

$$\left(\!\!{n \choose r}\!\!\right)=\binom{n+r-1}r$$

Thus your identity is equivalent to this other

$$\binom{n+r-1}r=\binom{n+r-2}{r-1}+\binom{n+r-2}{r}$$

Then naming $m:=n+r-1$ your identity is equivalent to prove that

$$\binom{m}r=\binom{m-1}{r-1}+\binom{m-1}r$$

what can be proved easily from the definition of binomial coefficient, that is

$$\binom{m-1}{r-1}+\binom{m-1}r=\frac{(m-1)!}{(r-1)!(m-r)!}+\frac{(m-1)!}{r!(m-r-1)!}\\=\frac{(m-1)!(r+m-r)}{r!(m-r)!}=\frac{m!}{r!(m-r)!}=\binom{m}r$$

$\endgroup$

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.