Multinomial theorem
From Freepedia
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 k1 through km such that k1 + k2 + k3 + ... + km = 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 k1 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>
- <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>
See also
This article incorporates material from multinomial theorem (proof) on PlanetMath, which is licensed under the GFDL.
