Multinomial theorem

From Wikipedia, the free encyclopedia

In mathematics, the multinomial theorem is an expression of a power of a sum in terms of powers of the addends. For any positive integer m and any nonnegative integer n, the multinomial formula is

$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1,k_2,\ldots,k_m} {n \choose k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}.$

The summation is taken over all sequences of nonnegative integer indices k₁ through k_m such that $\sum_{i=1}^m {k_i} = n$ . As with the binomial theorem, quantities of the form 0⁰ which appear are taken to equal 1.

The numbers

${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} = \prod_{i=1}^m {\sum_{j=1}^i k_j \choose k_i}$

are the multinomial coefficients.

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

In addition, 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 I's, 4 S's, and 2 P's is

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

The binomial theorem and binomial coefficients are special cases, for m = 2, of the multinomial theorem and multinomial coefficients, respectively.

[edit] Proof

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

First, for m = 1, both sides equal $x_1^n$ . For the induction step, suppose the multinomial theorem holds for m. Then

$(x_1+x_2+\cdots+x_m+x_{m+1})^n = (x_1+x_2+\cdots+(x_m+x_{m+1}))^n$

$= \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$

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

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

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