Multinomial theorem

Template:Short description

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: $(x_{1} + x_{2} + \dots + x_{m})^{n} = \sum_{\begin{matrix} k_{1} + k_{2} + \dots + k_{m} = n \\ k_{1}, k_{2}, \dots, k_{m} \geq 0 \end{matrix}} (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) x_{1}^{k_{1}} \cdot x_{2}^{k_{2}} \dots x_{m}^{k_{m}}$ where $(\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) = \frac{n!}{k_{1}! k_{2}! \dots k_{m}!}$ is a multinomial coefficient.^[1] 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.^[2]Template:Efn

In the case Template:Math, this statement reduces to that of the binomial theorem.^[2]

Example

The third power of the trinomial Template:Math is given by $(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 .$ 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 $a^{2} b^{0} c^{1}$ has coefficient $(\binom{3}{2, 0, 1}) = \frac{3!}{2! \cdot 0! \cdot 1!} = \frac{6}{2 \cdot 1 \cdot 1} = 3$ , the term $a^{1} b^{1} c^{1}$ has coefficient $(\binom{3}{1, 1, 1}) = \frac{3!}{1! \cdot 1! \cdot 1!} = \frac{6}{1 \cdot 1 \cdot 1} = 6$ , and so on.

Alternate expression

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

(x_{1} + \dots + x_{m})^{n} = \sum_{| α | = n} (\binom{n}{α}) x^{α}

where

α = (α_{1}, α_{2}, \dots, α_{m})

and

x^{α} = x_{1}^{α_{1}} x_{2}^{α_{2}} \dots x_{m}^{α_{m}}

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

\begin{matrix} (x_{1} + x_{2} + \dots + x_{m} + x_{m + 1})^{n} = (x_{1} + x_{2} + \dots + (x_{m} + x_{m + 1}))^{n} \\ = & \sum_{k_{1} + k_{2} + \dots + k_{m - 1} + K = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, K}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m - 1}^{k_{m - 1}} (x_{m} + x_{m + 1})^{K} \end{matrix}

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

= \sum_{k_{1} + k_{2} + \dots + k_{m - 1} + K = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, K}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m - 1}^{k_{m - 1}} \sum_{k_{m} + k_{m + 1} = K} (\binom{K}{k_{m}, k_{m + 1}}) x_{m}^{k_{m}} x_{m + 1}^{k_{m + 1}}

= \sum_{k_{1} + k_{2} + \dots + k_{m - 1} + k_{m} + k_{m + 1} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, k_{m}, k_{m + 1}}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots 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

(\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, K}) (\binom{K}{k_{m}, k_{m + 1}}) = (\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, k_{m}, k_{m + 1}}),

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

\frac{n!}{k_{1}! k_{2}! \dots k_{m - 1}! K!} \frac{K!}{k_{m}! k_{m + 1}!} = \frac{n!}{k_{1}! k_{2}! \dots k_{m + 1}!} .

Multinomial coefficients

The numbers

(\binom{n}{k_{1}, k_{2}, \dots, k_{m}})

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:

(\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) = \frac{n!}{k_{1}! k_{2}! \dots k_{m}!} = (\binom{k_{1}}{k_{1}}) (\binom{k_{1} + k_{2}}{k_{2}}) \dots (\binom{k_{1} + k_{2} + \dots + k_{m}}{k_{m}})

Sum of all multinomial coefficients

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

\sum_{k_{1} + k_{2} + \dots + k_{m} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m}^{k_{m}} = (x_{1} + x_{2} + \dots + x_{m})^{n}

gives immediately that

\sum_{k_{1} + k_{2} + \dots + k_{m} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) = m^{n} .

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:

#_{n, m} = (\binom{n + m - 1}{m - 1}) .

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, $\log (\binom{k n}{n, n, \dots, n}) = k n \log (k) + \frac{1}{2} (\log (k) - (k - 1) \log (2 π n)) - \frac{k^{2} - 1}{12 k n} + \frac{k^{4} - 1}{360 k^{3} n^{3}} - \frac{k^{6} - 1}{1260 k^{5} n^{5}} + O (\frac{1}{n^{6}})$ so for example, $(\binom{2 n}{n}) \sim \frac{2^{2 n}}{\sqrt{n π}}$

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.^[3]

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 $(\binom{N}{n_{1}})$ ways.
From the remaining Template:Math items choose Template:Math to label 2. This can be done $(\binom{N - n_{1}}{n_{2}})$ ways.
From the remaining Template:Math items choose Template:Math to label 3. Again, this can be done $(\binom{N - n_{1} - n_{2}}{n_{3}})$ ways.

Multiplying the number of choices at each step results in:

(\binom{N}{n_{1}}) (\binom{N - n_{1}}{n_{2}}) (\binom{N - n_{1} - n_{2}}{n_{3}}) \dots = \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}!} \dots .

Cancellation results in the formula given above.

Number of unique permutations of words

The multinomial coefficient

(\binom{n}{k_{1}, \dots, k_{m}})

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

(\binom{11}{1, 4, 4, 2}) = \frac{11!}{1! 4! 4! 2!} = 34650 .

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.

References

Template:Notelist Template:Reflist

[1] Template:Citation

[EC1-2] 2.0 ^2.1 Template:Citation

[3] Template:Cite web

[1]

[2]

[3]

Multinomial theorem

Contents

Theorem

Example

Alternate expression

Proof

Multinomial coefficients

Sum of all multinomial coefficients

Number of multinomial coefficients

Valuation of multinomial coefficients

Asymptotics

Interpretations

Ways to put objects into bins

Number of ways to select according to a distribution

Number of unique permutations of words

Generalized Pascal's triangle

See also

References

Navigation menu

Multinomial theorem

Theorem

Example

Alternate expression

Proof

Multinomial coefficients

Sum of all multinomial coefficients

Number of multinomial coefficients

Valuation of multinomial coefficients

Asymptotics

Interpretations

Ways to put objects into bins

Number of ways to select according to a distribution

Number of unique permutations of words

Generalized Pascal's triangle

See also

References

Navigation menu

Search