Proving Multinomial Theorem

Posted on February 23, 2015 by Sumant Sumant

Well if you understand Binomial expression \binom {n}{r}. It basically partitions a set in to two subsets with one set containing r elements and other set containing n-r elements. What if we want to partition a set in to k sets with n_1,n_2,...,n_k elements in each set. We can use fundamental principle of counting. The first set of n_1 elements can be carved out by \binom{n}{n_1}. The second from the remaining elements \binom{n-n_1}{n_2}. The third as \binom{n-n_1-n_2}{n_3} and so on till the last one will be \binom {n-n1-n_2-...-n_{k-1}}{n_k}. Using fundamental principle of counting we get. \binom{n}{n_1}\cdot\binom{n-n_1}{n_2}\cdot\binom{n-n_1-n_2}{n_3}\cdot\cdot\cdot\binom {n-n1-n_2-...-n_{k-1}}{n_k}

\Rightarrow \frac{n!}{(n-n_1)!n_1!} \cdot \frac{(n-n_1)!}{(n-n_1-n_2)!n_2!} \cdot \frac{(n-n_1-n_2)!}{(n-n_1-n_2-n_3)! n_3!}\cdot\cdot\cdot\frac{(n-n_1-n_2-\cdot\cdot\cdot n_{k-1})!}{(n-n_1-n_2-n_3-\cdot\cdot\cdot-n_{k-1}-n_k)! n_k!}

\Rightarrow \frac{n!}{n_1!n_2!n_3!\cdot\cdot\cdot n_k!}

About Sumant Sumant

I love Math and I am always looking forward to collaborate with fellow learners. If you need help learning math then please do contact me.
This entry was posted in Combinatorics, Proof. Bookmark the permalink.

Leave a comment