Online Course Discussion Forum

Question 6.25 for MC II-A Combinatorics

 
 
Picture of Areteem Professor
Re: Question 6.25 for MC II-A Combinatorics
by Areteem Professor - Tuesday, January 28, 2020, 10:32 AM
 

For this problem you want to prove that in $(a_1 + a_2 + \cdots + a_j)^n$, the coefficient of $a_1^{k_1}a_2^{k_2}\cdots a_j^{k_j}$, where $k_1 + k_2 + \cdots + k_j = n$ is equal to $$\dfrac{n!}{(k_1!)\cdot (k_2!)\cdots (k_j!)}.$$

Let $k_1 + k_2 + \cdots + k_j = n$ and consider all the words of length $n$ with letters $a_1, a_2, \dots, a_j$, where $a_i$ occurs $k_j$ times.  For each of these words there will be an occurrence of $a_1^{k_1}a_2^{k_2}\cdots a_j^{k_j}$ when we expand $(a_1 + a_2 + \cdots + a_j)^n$.