Multinomial theorem

Encyclopedia : M : MU : MUL : Multinomial theorem

In mathematics, the multinomial formula 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 + x_3 + \cdots + x_m)^n = \sum_ x_1^ x_2^ x_3^ \cdots x_m^ ]

The summation is taken over all sequences of nonnegative integer indices k₁ through k_m such that k₁ + k₂ + k₃ + ... + k_m = n. The numbers

[ = \frac]

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₁ 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_)^n] [ =] [ \sum_^n (x_1+\cdots + x_k)^l x_^]

:[ =] [ \sum_^n l! \sum_ \frac x_^]

[ Note: Binomial theorem used to go from [ sum_^n (x_1+cdots + x_k)^l ] to [ sum_^n l! sum_ frac ] Sub-Note: l! represents the numerator of each coefficient in the summation, and i! in the summation represents the denomonator of each coefficient in the summation. x^i represents each variable in the expansion. The summation allows all the different i to add up to l.

i.e. With p + q + r = n, (a + b + c)^n = [sum_ fraca^p*b^q*c^r]
Reference: http://mathcentral.uregina.ca/QQ/database/QQ.09.99/das1.html ]

:[ =] [ n! \sum_^n \sum_ \frac^}]

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] [ =] [ \_+ \mid l=0,\ldots, n,\, \vert(i_1,\ldots, i_k)\vert=l \}],

[ B] [ =] [ \_+ \mid \vert j\vert=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_) \in I^_+], and [\vert j\vert=n].

Let [l=\vert(j_1,\ldots, j_k)\vert]. Then [l=n-j_], so [j_ = n-l] for some [l=0,\ldots, n]. It follows that that [A=B].

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

[ (x_1+\cdots + x_)^n] [ =] [ n! \sum_ \frac x_^}}!}]

:[ =] [ n! \sum_ \frac].

This completes the proof. [\Box]

Note2: [ i = (i_1,\ldots, i_k) = (j_1,\ldots, j_k) ] intuitively. I think it would've been easier had they just replaced "n - l" with j_(k+1), but that would've been harder to understand and not broken down as much.

Multinomial theorem

Proof

See also