Multinomial theorem

Template:More citations needed In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials.

Theorem

For any positive integer Template:Mvar and any non-negative integer Template:Mvar, the multinomial theorem describes how a sum with Template:Mvar terms expands when raised to the Template:Mvarth power: <math display="block">(x_1 + x_2 + \cdots + x_m)^n

= \sum_{\begin{array}{c} k_1+k_2+\cdots+k_m=n \\ k_1, k_2, \cdots, k_m \geq 0\end{array}} {n \choose k_1, k_2, \ldots, k_m}
 x_1^{k_1} \cdot x_2^{k_2} \cdots x_m^{k_m}</math>

where <math display="block"> {n \choose k_1, k_2, \ldots, k_m}

= \frac{n!}{k_1!\, k_2! \cdots k_m!}</math>

is a multinomial coefficient.<ref>Template:Citation</ref> The sum is taken over all combinations of nonnegative integer indices Template:Math through Template:Mvar such that the sum of all Template:Mvar is Template:Mvar. That is, for each term in the expansion, the exponents of the Template:Mvar must add up to Template:Mvar.<ref name="EC1">Template:Citation</ref>Template:Efn

In the case Template:Math, this statement reduces to that of the binomial theorem.<ref name="EC1" />

Example

The third power of the trinomial Template:Math is given by <math display="block"> (a+b+c)^3 = a^3 + b^3 + c^3 + 3 a^2 b + 3 a^2 c + 3 b^2 a + 3 b^2 c + 3 c^2 a + 3 c^2 b + 6 a b c. </math> This can be computed by hand using the distributive property of multiplication over addition and combining like terms, but it can also be done (perhaps more easily) with the multinomial theorem. It is possible to "read off" the multinomial coefficients from the terms by using the multinomial coefficient formula. For example, the term <math>a^2 b^0 c^1 </math> has coefficient <math>{3 \choose 2, 0, 1} = \frac{3!}{2!\cdot 0!\cdot 1!} = \frac{6}{2 \cdot 1 \cdot 1} = 3</math>, the term <math>a^1 b^1 c^1</math> has coefficient <math>{3 \choose 1, 1, 1} = \frac{3!}{1!\cdot 1!\cdot 1!} = \frac{6}{1 \cdot 1 \cdot 1} = 6</math>, and so on.

Alternate expression

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

<math>(x_1+\cdots+x_m)^n = \sum_{|\alpha|=n}{n \choose \alpha}x^\alpha</math>

where

<math>

\alpha=(\alpha_1,\alpha_2,\dots,\alpha_m) </math> and

<math>

x^\alpha=x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_m^{\alpha_m} </math>

Proof

This proof of the multinomial theorem uses the binomial theorem and induction on Template:Mvar.

First, for Template:Math, both sides equal Template:Math since there is only one term Template:Math in the sum. For the induction step, suppose the multinomial theorem holds for Template:Mvar. Then

<math>

\begin{align} & (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{align} </math>

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

<math> = \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}}</math>

<math> = \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}}

</math>

which completes the induction. The last step follows because

<math>{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}},</math>

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

<math> \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}!}.</math>

Multinomial coefficients

The numbers

<math> {n \choose k_1, k_2, \ldots, k_m}</math>

appearing in the theorem are the multinomial coefficients. They can be expressed in numerous ways, including as a product of binomial coefficients or of factorials:

<math>

{n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!} = {k_1\choose k_1}{k_1+k_2\choose k_2}\cdots{k_1+k_2+\cdots+k_m\choose k_m}

</math>

Sum of all multinomial coefficients

The substitution of Template:Math for all Template:Mvar into the multinomial theorem

<math>\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</math> gives immediately that

<math>

\sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} = m^n. </math>

Number of multinomial coefficients

The number of terms in a multinomial sum, Template:Math, is equal to the number of monomials of degree Template:Mvar on the variables Template:Math:

<math>

\#_{n,m} = {n+m-1 \choose m-1}. </math>

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

Valuation of multinomial coefficients

The largest power of a prime Template:Mvar that divides a multinomial coefficient may be computed using a generalization of Kummer's theorem.

Asymptotics

By Stirling's approximation, or equivalently the log-gamma function's asymptotic expansion, <math display="block">\log\binom{kn}{n, n, \cdots, n} = k n \log(k) + \frac{1}{2} \left(\log(k) - (k - 1) \log(2 \pi n)\right) - \frac{k^2 - 1}{12kn} + \frac{k^4 - 1}{360k^3n^3} - \frac{k^6 - 1}{1260k^5n^5} + O\left(\frac{1}{n^6}\right)</math>so for example,<math display="block">\binom{2n}{n} \sim \frac{2^{2n}}{\sqrt{n\pi }}</math>

Interpretations

Ways to put objects into bins

The multinomial coefficients have a direct combinatorial interpretation, as the number of ways of depositing Template:Mvar distinct objects into Template:Mvar distinct bins, with Template:Math objects in the first bin, Template:Math objects in the second bin, and so on.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Number of ways to select according to a distribution

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 Template:Math on a set of Template:Mvar total items, Template:Mvar represents the number of items to be given the label Template:Mvar. (In statistical mechanics Template:Mvar is the label of the energy state.)

The number of arrangements is found by

• Choosing Template:Math of the total Template:Mvar to be labeled 1. This can be done <math>\tbinom{N}{n_1}</math> ways.
• From the remaining Template:Math items choose Template:Math to label 2. This can be done <math>\tbinom{N-n_1}{n_2}</math> ways.
• From the remaining Template:Math items choose Template:Math to label 3. Again, this can be done <math>\tbinom{N-n_1-n_2}{n_3}</math> ways.

Multiplying the number of choices at each step results in:

<math>{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.</math>

Cancellation results in the formula given above.

Number of unique permutations of words

File:Multinomial theorem mississippi.svg

Multinomial coefficient as a product of binomial coefficients, counting the permutations of the letters of MISSISSIPPI.

The multinomial coefficient

<math>\binom{n}{k_1, \ldots, k_m}</math>

is also the number of distinct ways to permute a multiset of Template:Mvar elements, where Template:Mvar is the multiplicity of each of the Template:Mvarth element. 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

<math>{11 \choose 1, 4, 4, 2} = \frac{11!}{1!\, 4!\, 4!\, 2!} = 34650.</math>

Generalized Pascal's triangle

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.

See also

• Multinomial distribution
• Stars and bars (combinatorics)