Prove that the multinomial coefficient given by:
$$
\binom{n}{n_1}\binom{n-n_1}{n_2}\binom{n-n_1-n_2}{n_3}\cdots\binom{n-n_1-n_2-\dots-n_{k-1}}{n_k}
$$
equals the following expression
$$
\frac{n!}{n_1!n_2!n_3!\cdots n_k!}
$$
Thank you for any help you can give me
Best Answer
Just write it out and see that most terms cancel out.
$$ {n \choose n_1}{n-n_1\choose n_2}\cdots{n-n_1-n_2-\cdots n_{k-2} \choose n_{k-1}}{n-n_1-n_2-\cdots n_{k-2}-n_{k-1} \choose n_{k}} $$
Let's look at the first part:
$$ {n \choose n_1}{n-n_1\choose n_2}=\frac{n!}{n_1!(n-n_1)!}\frac{(n-n_1)!}{n_2!(n-n_1-n_2)!}=\frac{n!}{n_1!n_2!(n-n_1-n_2)!} $$
and then with the next term: $$ {n \choose n_1}{n-n_1\choose n_2}{n-n_1-n_2\choose n_3}=\frac{n!}{n_1!n_2!(n-n_1-n_2)!}\frac{(n-n_1-n_2)!}{n_3!(n-n_1-n_2-n_3)!}=\frac{n!}{n_1!n_2!n_3!(n-n_1-n_2-n_3)!} $$
and that way it continues. In the end you will have
$$ {n \choose n_1}\cdots{n-n_1-n_2-\cdots n_{k-2}-n_{k-1} \choose n_{k}}=\frac{n!}{n_1!n_2!\cdots n_{k-1}!(n-n_1-n_2-\cdots-n_{k-1})!}\frac{(n-n_1-n_2-\cdots-n_{k-1})!}{n_k!(n-n_1-n_2-\cdots-n_{k})!}=\frac{n!}{n_1!n_2!\cdots n_k!}\frac{1}{(n-n_1-n_2-\cdots-n_k)!} $$
However, since $$ n=\sum_{i=1}^kn_i $$ it follows that
$$ (n-n_1-n_2-\cdots-n_k)!=1 $$ and the result is that
$$ {n \choose n_1}\cdots{n-n_1-n_2-\cdots n_{k-2}-n_{k-1} \choose n_{k}}=\frac{n!}{n_1!n_2!\cdots n_k!}. $$