Multinomial theorem

From Free net encyclopedia

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

<math>(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} </math>

The summation is taken over all combinations of the indices k₁ through k_m such that k₁ + k₂ + k₃ + ... + k_m = n; some or all of the nonnegative indices may be zero. The numbers

<math> {n \choose k_1, k_2, k_3, \ldots, k_m}

= \frac{n!}{k_1! k_2! k_3! \cdots k_m!}</math>

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 <math>k</math>. In addition, we shall use multi-index notation.

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

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

<math> =</math> <math> \sum_{l=0}^n {n \choose l} l! \sum_{\vert i\vert=l} \frac{x^i}{i!} x_{k+1}^{n-l}</math>

[ Note: Binomial theorem used to go from <math> \sum_{l=0}^n {n \choose l} (x_1+\cdots + x_k)^l </math> to <math> \sum_{l=0}^n {n \choose l} l! \sum_{\vert i\vert=l} \frac{x^i}{i!} </math> 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 = <math>\sum_{} \frac{n!}{p!q!r!}a^p*b^q*c^r</math>
Reference: http://mathcentral.uregina.ca/QQ/database/QQ.09.99/das1.html ]

<math> =</math> <math> n! \sum_{l=0}^n \sum_{\vert i\vert=l} \frac{x^i x_{k+1}^{n-l}}{i! (n-l)!}</math>

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

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

<math> B</math> <math> =</math> <math> \{j \in I^{k+1}_+ \mid \vert j\vert=n \}</math>

are equal. The inclusion <math>A \subset B</math> is clear since

<math> \vert(i_1,\ldots,i_k, n-l)\vert = l + n-l = n</math>.

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

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

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

<math> (x_1+\cdots + x_{k+1})^n</math> <math> =</math> <math> n! \sum_{\vert j\vert=n} \frac{x^{(j_1,\ldots, j_k)} x_{k+1}^{j_{k+1}}}{(j_1,\ldots, j_k)! j_{k+1}!}</math>

<math> =</math> <math> n! \sum_{\vert j\vert=n} \frac{y^j}{j!}</math>.

This completes the proof. <math>\Box</math>

Note2: <math> i = (i_1,\ldots, i_k) = (j_1,\ldots, j_k) </math> 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.

See also

• Multinomial distribution

Template:Planetmathfr:Formule du multinôme de Newton ru:Мультиномиальный коэффициент