In mathematics, the multinomial formula is an expression of a power (mathematics) 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 + x_3 + cdots + x_m)^n = sum_{k_1,k_2,k_3,ldots,k_m} {n choose k_1, k_2, k_3, ldots, k_m} x_1^{k_1} x_2^{k_2} x_3^{k_3} cdots x_m^{k_m}

The summation is taken over all combinations of the indices k 1 through k m such that k 1 + k 2 + k 3 + ... + k m = n ; some or all of the nonnegative indices may be zero. The numbers

: {n choose k_1, k_2, k_3, ldots, k_m} = frac{n!}{k_1! k_2! k_3! cdots k_m!}

are the multinomial coefficients .

The multinomial coefficients have a direct combinatorial interpretation, as the number of ways of depositing n distinguished objects in m bins, with k 1 in the first, and so on. This is an equivalent assertion.

The binomial theorem and binomial coefficient are special cases, for m = 2, of the multinomial formula and multinomial coefficient, respectively. Therefore this is also called the multinomial theorem .

=Proof=

This proof of the multinomial theorem uses the binomial theorem and induction on k. In addition, we shall use multi-index notation.

First, for k=1, both sides equal x_1^n. For the induction step, suppose the multinomial theorem holds for k. Then the binomial theorem and the induction assumption yield

(x_1+cdots + x_k,+,x_{k+1})^n = sum_{l=0}^n {n choose l} (x_1+cdots + x_k)^l x_{k+1}^{n-l}

:: = sum_{l=0}^n {n choose l} l! sum_{vert ivert=l} frac{x^i}{i!} x_{k+1}^{n-l}

:: = n! sum_{l=0}^n sum_{vert ivert=l} frac{x^i x_{k+1}^{n-l}}{i! (n-l)!}

where x=(x_1,ldots, x_k) and i is a multi-index in I^k_+. To complete the proof, we need to show that the sets

A = { (i_1,ldots,i_k, n-l)in I^{k+1}_+ mid l=0,ldots, n,, vert(i_1,ldots, i_k)vert=l },

B = {j in I^{k+1}_+ mid vert jvert=n }

are equal. The inclusion A subset B is clear since

vert(i_1,ldots,i_k, n-l)vert = l + n-l = n.

For B subset A, suppose j=(j_1,ldots, j_{k+1}) in I^{k+1}_+, and vert jvert=n.

Let l=vert(j_1,ldots, j_k)vert. Then l=n-j_{k+1}, so j_{k+1} = n-l for some l=0,ldots, n. It follows that that A=B.

Let us define y=(x_1,cdots, x_{k+1}) and let j=(j_1,ldots, j_{k+1}) be a multi-index in I_+^{k+1}. Then

(x_1+cdots + x_{k+1})^n = n! sum_{vert jvert=n} frac{x^{(j_1,ldots, j_k)} x_{k+1}^{j_{k+1}}}{(j_1,ldots, j_k)! j_{k+1}!}

:: = n! sum_{vert jvert=n} frac{y^j}{j!}.

This completes the proof. Box

= See also =