Editing Multinomial theorem (section)

==Theorem==
For any positive integer {{mvar|m}} and any non-negative integer {{mvar|n}}, the multinomial theorem describes how a sum with {{mvar|m}} terms expands when raised to the {{mvar|n}}th power:
<math display="block">(x_1 + x_2  + \cdots + x_m)^n
 = \sum_{\begin{array}{c} k_1+k_2+\cdots+k_m=n \\ k_1, k_2, \cdots, k_m \geq 0\end{array}} {n \choose k_1, k_2, \ldots, k_m}
  x_1^{k_1} \cdot x_2^{k_2} \cdots x_m^{k_m}</math>
where
<math display="block"> {n \choose k_1, k_2, \ldots, k_m}
 = \frac{n!}{k_1!\, k_2! \cdots k_m!}</math>
is a '''multinomial coefficient'''.<ref>{{citation |first=Martin |last=Aigner |author-link=Martin Aigner |title=Combinatorial Theory |year=1997 |publisher=Springer |page=77 }}</ref> The sum is taken over all combinations of [[nonnegative]] [[integer]] indices {{math|''k''{{sub|1}}}} through {{mvar|k{{sub|m}}}} such that the sum of all {{mvar|k{{sub|i}}}} is {{mvar|n}}.  That is, for each term in the expansion, the exponents of the {{mvar|x{{sub|i}}}} must add up to {{mvar|n}}.<ref name="EC1">{{citation |last = Stanley | first = Richard | author-link = Richard P. Stanley | title = Enumerative Combinatorics | volume = 1 | edition = 2 | at = §1.2 | publisher = Cambridge University Press|  year = 2012}}</ref>{{efn|As with the [[binomial theorem]], quantities of the form {{math|''x''{{sup|0}}}} that appear are taken to equal 1, [[Zero to the power of zero|even when {{mvar|x}} equals zero]].}}

In the case {{math|1=''m'' = 2}}, this statement reduces to that of the [[binomial theorem]].<ref name="EC1" />

===Example===
The third power of the trinomial {{math|''a'' + ''b'' + ''c''}} is given by
<math display="block">
(a+b+c)^3 = a^3 + b^3 + c^3 + 3 a^2 b + 3 a^2 c + 3 b^2 a + 3 b^2 c + 3 c^2 a + 3 c^2 b + 6 a b c.
</math>
This can be computed by hand using the [[distributive property]] of multiplication over addition and combining like terms, but it can also be done (perhaps more easily) with the multinomial theorem. It is possible to "read off" the multinomial coefficients from the terms by using the multinomial coefficient formula. For example, the term <math>a^2 b^0 c^1 </math> has coefficient <math>{3 \choose 2, 0, 1} = \frac{3!}{2!\cdot 0!\cdot 1!} = \frac{6}{2 \cdot 1 \cdot 1} = 3</math>, the term <math>a^1 b^1 c^1</math> has coefficient <math>{3 \choose 1, 1, 1} = \frac{3!}{1!\cdot 1!\cdot 1!} = \frac{6}{1 \cdot 1 \cdot 1} = 6</math>, and so on.

===Alternate expression===
The statement of the theorem can be written concisely using [[multiindices]]:

:<math>(x_1+\cdots+x_m)^n = \sum_{|\alpha|=n}{n \choose \alpha}x^\alpha</math>

where

:<math>
\alpha=(\alpha_1,\alpha_2,\dots,\alpha_m)
</math>
and
:<math>
x^\alpha=x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_m^{\alpha_m}
</math>

===Proof===
This proof of the multinomial theorem uses the [[binomial theorem]] and [[Mathematical induction|induction]] on {{mvar|m}}.

First, for {{math|1=''m'' = 1}}, both sides equal {{math|''x''{{sub|1}}{{sup|''n''}}}} since there is only one term {{math|1=''k''{{sub|1}} = ''n''}} in the sum. For the induction step, suppose the multinomial theorem holds for {{mvar|m}}.  Then

: <math>
\begin{align}
& (x_1+x_2+\cdots+x_m+x_{m+1})^n = (x_1+x_2+\cdots+(x_m+x_{m+1}))^n \\[6pt]
= {} & \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
\end{align}
</math>

by the induction hypothesis.  Applying the binomial theorem to the last factor,

:<math> = \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}}</math>
:<math> = \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}}
</math>

which completes the induction.  The last step follows because

:<math>{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}},</math>
as can easily be seen by writing the three coefficients using factorials as follows:

:<math> \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}!}.</math>