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 k1 through km such that \sum_{i=1}^m {k_i} = n. As with the binomial theorem, quantities of the form 00 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 k1 objects in the first bin, k2 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 ki 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}}

which completes the induction. The last step follows because

{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:

 \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}!}

[edit] See also