I've been trying to rout out an exclusively combinatorial proof of the Multinomial Theorem with bounteous details but only lighted upon this one – see P2. Any other helpful ones?
$(x_1+\cdots+x_k)^n =$ Top of Page 39 from UNC:
$\sum\limits_{\large{(a_1, …, a_{k – 1}) \; \ni \; 0 \le a_1+…+ a_{k – 1} \le n}}\dbinom{n}{a_1,…,a_{k-1}}\cdot x_1^{a_1} \cdots x_{k-1}^{a_{k-1}}x_k^{\large{n – a_1 – \cdots – a_{k-1}}}$
$= \sum\limits_{\large{a_1+…+a_k = n \; \& \; a_i \ge 0 }}\dbinom{n}{a_1,…,a_k} x_1^{a_1} \cdots x_k^{a_k}$ Bottom of P1 from MSU.
I see that both are the Multinomial Theorem but which one is better?
I thought to try this myself, following the combinatorial proof of the Binomial Theorem. So esteem each term (in green) in $(x_1+\cdots+x_k)^n = \underbrace{\color{green}{[x_1+\cdots+x_k]…[x_1+\cdots+x_k]}}_{\text{n terms}}$ as one box from which to choose $x_1, …, x_k$.
Since each term/box (in green) contains $k$ terms, the total number of terms $ = k^n$.
First, consider $x_1$.
● For $x_1^n$, must have $a_ 1 = n\qquad \& \qquad a_2 = … = a_k = 0$.
● For $x_1^{n – 1}$, must have $a_1 = n – 1 \qquad \& \qquad a_2 \text{ OR } … \text{ OR } a_k = 1$
(the latter due to $a_1+…+a_k = n$ in definition from P1 of MSU)
…
● For $x_1^{1},$ must have $a_1 = 1 \qquad \& \qquad a_2 \text{ OR } … \text{ OR } a_k = n – 1$
● For $x_1^{0},$ must have $a_1 = 0 \qquad \& \qquad a_2 \text{ OR } … \text{ OR } a_k = n$
The above extends to and must hold for all $x_1, …, x_k$.
How to translate all this into combinatorial notation? How to forge ahead and complete please?
Best Answer
This is one approach: When you expand $(x_1+x_2+....+x_k)^n$ , you will have a collection of terms $c_ix_1^{n_1}x_2^{n_2}......x_k^{n_k}$ for each "box"/factor $i$ in your green, so that $n_1+n_2+..+n_k=n$.
For a fixed given $k$-tuple $(n_1,..,n_k)$ , the assignment of the $n_1, ..., n_k$ can be chosen in:
$\dbinom {n}{n_1} \times \dbinom {n-n_1}{n_2} \times.....\dbinom{n-n_1-....-n_{k-1}}{n_k}$ ways. The $n_1$ balls can be chosen from the original $n$. After having used up $n_1$ balls, you only have $n-n_1$ balls left, which you can use to choose the $n_2$ balls for $x_2$, etc.. This expansion is precisely the multinomial coefficient: $$\dbinom {n}{n_1,n_2,....,n_k} $$
The above is true only for the given $k$-tuple $(n_1,..,n_k)$. Now, we do the sum over all $k$-ples $(n_1, n_2,....,n_k)$ with $n_1+n_2+...+n_k=n$
The reason why we sum over all $k$-ples is that, when we expand the product :
$$ (x_1+x_2+...+ x_k)^n= \underbrace{(x_1 + x_2+...+x_k) (x_1+x_2...+x_k)....(x_1+x_2+..+x_k)}_{n \text{ times }}$$
, you will ultimately multiply one element $x_{j1}$ from the first copy of $(x_1+x_2+..+x_k)$ with one element $x_{j2}$ in the second copy,... with an $x_{jk}$ from the $k$-th copy of $(x_1+...+x_k)$,
i.e., the product will have one element of each copy of the sum.
Notice some specific cases/examples, for $k=n=3$; I think this will be clearer than a more formal argument:
$(\color{green}{x_1}+x_2+x_3)(x_1+x_2+x_3)(x_1+x_2+x_3)$ : We start with $\color{green}{x_1}$, multiply by some element $x_{j2}$ in the second parenthesis to get $x_1x_{j2}$, and then we multiply this $x_1x_{j2}$ by some element $x_{j3}$ in the third parenthesis (notice that we may have $x_{j2}=x_1, x_2$ or $x_3$). How many different monomials can we have? Well, each monomial will contain 3 terms, possibly repeated, so that the sum of the exponents of $x_1x_{j2}x_{j3}$ will add up to 3, e.g., we will have terms like $x_1x_1x_2=x_1^2x_2$, or $x_1^3$, or $x_1x_2x_3$, etc.
How many monomials of this sort can we have? Well, we can have as many as the number of all the 3-tuples (ie triples) of the exponents, $(n_1, n_2, n_3)$ chosen with ordering and with replacement, for the respective terms $x_1,x_2,x_3$, such that $n_1+n_2+n_3=3$ (because each monomial contains $k = 3$ terms).
Basically, we are summing over all strings $(x_1^{n_1}x_2^{n_2}...x_k^{n_k})$ , where all the exponents add-up to $n$; this amount of terms is equivalent to the number of solutions of the equation $x_1+ x_2+....+x_k =n$