Multinomial theorem

The third power of the trinomial a + b + c is given by

${\displaystyle (a+b+c)^{3}=a^{3}+b^{3}+c^{3}+3a^{2}b+3a^{2}c+3b^{2}a+3b^{2}c+3c^{2}a+3c^{2}b+6abc.}$

This can be computed by hand using the distributive property of multiplication over addition, but it can also be done (perhaps more easily) with the multinomial theorem, which gives a simple formula for any coefficient. It is possible to "read off" the multinomial coefficients from the terms by using the multinomial coefficient formula. For example:

${\displaystyle a^{2}b^{0}c^{1}}$ has the coefficient ${\displaystyle {3 \choose 2,0,1}={\frac {3!}{2!\cdot 0!\cdot 1!}}={\frac {6}{2\cdot 1\cdot 1}}=3.}$

${\displaystyle a^{1}b^{1}c^{1}}$ has the coefficient ${\displaystyle {3 \choose 1,1,1}={\frac {3!}{1!\cdot 1!\cdot 1!}}={\frac {6}{1\cdot 1\cdot 1}}=6.}$

The statement of the theorem can be written concisely using multiindices:

${\displaystyle (x_{1}+\cdots +x_{m})^{n}=\sum _{|\alpha |=n}{n \choose \alpha }x^{\alpha }}$

where

${\displaystyle \alpha =(\alpha _{1},\alpha _{2},\dots ,\alpha _{m})}$

and

${\displaystyle x^{\alpha }=x_{1}^{\alpha _{1}}x_{2}^{\alpha _{2}}\cdots x_{m}^{\alpha _{m}}}$

This proof of the multinomial theorem uses the binomial theorem and induction on m.

First, for m = 1, both sides equal x₁ⁿ since there is only one term k₁ = n in the sum. For the induction step, suppose the multinomial theorem holds for m. Then

${\displaystyle {\begin{aligned}&(x_{1}+x_{2}+\cdots +x_{m}+x_{m+1})^{n}=(x_{1}+x_{2}+\cdots +(x_{m}+x_{m+1}))^{n}\\[6pt]={}&\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},K}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}(x_{m}+x_{m+1})^{K}\end{aligned}}}$

by the induction hypothesis. Applying the binomial theorem to the last factor,

${\displaystyle =\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},K}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}\sum _{k_{m}+k_{m+1}=K}{K \choose k_{m},k_{m+1}}x_{m}^{k_{m}}x_{m+1}^{k_{m+1}}}$

${\displaystyle =\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+k_{m}+k_{m+1}=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},k_{m},k_{m+1}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}x_{m}^{k_{m}}x_{m+1}^{k_{m+1}}}$

which completes the induction. The last step follows because

${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m-1},K}{K \choose k_{m},k_{m+1}}={n \choose k_{1},k_{2},\ldots ,k_{m-1},k_{m},k_{m+1}},}$

as can easily be seen by writing the three coefficients using factorials as follows:

${\displaystyle {\frac {n!}{k_{1}!k_{2}!\cdots k_{m-1}!K!}}{\frac {K!}{k_{m}!k_{m+1}!}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{m+1}!}}.}$

The substitution of x_i = 1 for all i into the multinomial theorem

${\displaystyle \sum _{k_{1}+k_{2}+\cdots +k_{m}=n}{n \choose k_{1},k_{2},\ldots ,k_{m}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}=(x_{1}+x_{2}+\cdots +x_{m})^{n}}$

gives immediately that

${\displaystyle \sum _{k_{1}+k_{2}+\cdots +k_{m}=n}{n \choose k_{1},k_{2},\ldots ,k_{m}}=m^{n}.}$

The number of terms in a multinomial sum, #_n,m, is equal to the number of monomials of degree n on the variables x₁, …, x_m:

${\displaystyle \#_{n,m}={n+m-1 \choose m-1}.}$

The count can be performed easily using the method of stars and bars.

The largest power of a prime ${\displaystyle p}$ that divides a multinomial coefficient may be computed using a generalization of Kummer's theorem.

The multinomial coefficients have a direct combinatorial interpretation, as the number of ways of depositing n distinct objects into m distinct bins, with k₁ objects in the first bin, k₂ objects in the second bin, and so on.[1]

In statistical mechanics and combinatorics if one has a number distribution of labels then the multinomial coefficients naturally arise from the binomial coefficients. Given a number distribution {n_i} on a set of N total items, n_i represents the number of items to be given the label i. (In statistical mechanics i is the label of the energy state.)

The number of arrangements is found by

• Choosing n₁ of the total N to be labeled 1. This can be done ${\displaystyle N \choose n_{1}}$ ways.
• From the remaining N − n₁ items choose n₂ to label 2. This can be done ${\displaystyle N-n_{1} \choose n_{2}}$ ways.
• From the remaining N − n₁ − n₂ items choose n₃ to label 3. Again, this can be done ${\displaystyle N-n_{1}-n_{2} \choose n_{3}}$ ways.

Multiplying the number of choices at each step results in:

${\displaystyle {N \choose n_{1}}{N-n_{1} \choose n_{2}}{N-n_{1}-n_{2} \choose n_{3}}\cdots ={\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}!}}\cdots .}$

Cancellation results in the formula given in introduction.

The multinomial coefficient is also the number of distinct ways to permute a multiset of n elements, and k_i are the multiplicities of each of the distinct elements. For example, the number of distinct permutations of the letters of the word MISSISSIPPI, which has 1 M, 4 Is, 4 Ss, and 2 Ps is

${\displaystyle {11 \choose 1,4,4,2}={\frac {11!}{1!\,4!\,4!\,2!}}=34650.}$

Proof:

Let the number of arrangements possible be ${\displaystyle x}$.

If all the letters were distinct, for each one of ${\displaystyle x}$ arrangements, there would be ${\displaystyle 1!}$ ways of arranging ${\displaystyle 1\ M}$, ${\displaystyle 4!}$ ways of arranging ${\displaystyle 4\ I's}$, ${\displaystyle 4!}$ ways of arranging ${\displaystyle 4\ S's}$ and ${\displaystyle 2!}$ ways of arranging ${\displaystyle 2\ P's}$.

${\displaystyle \therefore x\ \cdot \ (1!)\ \cdot \ (4!)\ \cdot \ (4!)\ \cdot \ (2!)=11!}$

${\displaystyle \implies x={\frac {11!}{1!\cdot 4!\cdot 4!\cdot 2!}}=34650}$

One can use the multinomial theorem to generalize Pascal's triangle or Pascal's pyramid to Pascal's simplex. This provides a quick way to generate a lookup table for multinomial coefficients.