Combinatorial Proof of Multinomial Theorem - Without Induction or Binomial Theorem

Question

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?

Answer 1

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$

Answer 2

Let $n$ be a positive integer. For all $x_1$, $x_2$,..., $x_k$, $$(x_1+x_2+\cdots +x_k)^n=\sum {n\choose n_1,n_2,...,n_k}x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k},$$ where the summation extends over all non-negative integral solutions $n_1,n_2,...,n_k$ of $n_1+n_2+\cdots +n_k=n$.

Write $(x_1+x_2+\cdots +x_k)^n$ as the product of $n$ factors where each factor is $(x_1+x_2+\cdots +x_k)$. Using the distributive law we can expand this product and collect like terms. For each of the n factors we can choose one of the the $k$ numbers $x_1,x_2,...,x_k$ and form their product for $k^n$ terms. Each of these terms can be arranged in the form $x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k}$, where the non-negative integer exponents $n_1,n_2,...,n_k$ sum to $n$ We obtain this by noticing that we can choose $x_1$ in $n_1$ ways of the $n$ factors, $x_2$ in $n_2$ ways of the remaining $n-n_1$ factors,..., $x_k$ in $n_k$ ways of the remaining $n-n_1-\cdots -n_k-1$ factors. Using the Multiplication Principle, we see that the number of times the term $x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k}$ occurs is $${n\choose n_1}{n-n_1\choose n_2}\cdots {n-n_1-\cdots {n_{k-1}}\choose n_k}={n\choose n_1,n_2,...,n_k}.$$ Thus $$(x_1+x_2+\cdots +x_k)^n=\sum {n\choose n_1,n_2,...,n_k}x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k}.$$

Answer 3

The multinomial theorem says that for commuting quantities $X_1,\ldots,X_n$ in a ring one has $$ (X_1+\cdots+X_k)^n=\sum_{\substack{a_1,\ldots,a_k\in\Bbb N\\a_1+\cdots+a_k=n}} \binom n{a_1,\ldots,a_k}X_1^{a_1}\ldots X_k^{a_k} $$ where the multinomial coefficient $\binom n{a_1,\ldots,a_k}$ can be defined (under the hypothesis $a_1+\cdots+a_k=n$, without which it is either left undefined, or maybe set to$~0$), either combinatorially as the number of words (of length$~n$) over the alphabet $\{A_1,\ldots,A_k\}$ containing $a_i$ copies of the letter$~A_i$ for $i=1,\ldots,k$, or algebraically as $\frac{n!}{a_1!\ldots a_k!}$.

A combinatorial proof of the multinomial theorem would naturally use the combinatorial description of multinomial coefficients. It is almost a triviality: without assuming that the $X_i$ commute, the $n$-th power can be expanded by the distributive laws to a sum of $k^n$ distinct monomials in the $X_i$, which are just all distinct words of length $n$ that can be formed from them; now assuming commutation, one groups together all words that have the same number of copies of each$~X_i$, and if those multiplicities are $a_1,\ldots,a_k$ respectively, then one gets $\binom n{a_1,\ldots,a_k}$ times the monomial $X_1^{a_1}\ldots X_k^{a_k}$.

The equivalence of the combinatorial and algebraic description of multinomial coefficients is another matter, but also quite simple. For a word of length$~n$ with given multiplicities $a_1,\ldots,a_k$ of individual letters, the $n!$ permutations of the letters of the word certainly generate all words that can be made from that multiset of letters, but each word is obtained multiple times. To obtain from one way to generate a word all other ways to generate the same word, one can independently permute all copies of a same letter among each other, which can be done in $a_1!\ldots a_k!$ ways. This means there are$\frac{n!}{a_1!\ldots a_k!}$ distinct words.