# Talk:Multinomial theorem

## Proof

"Elegant simple proof" is incomplete. It only does induction on n, and fails to do induction on m. Also having summations explicitly inside indexes of summations is hardly "simple". The multiindex version is much more elegant and the proof now does induction on n and m. RobotMacheen (talk) 14:45, 16 November 2008 (UTC)

To make it more explicit. Say P(n,m) is the statement of the multinomial theorem, where n is the exponent, and m is the number of terms being added. We need to prove that P(n,m) is equivalent to P(n+1,m) and P(n,m+1), along with proving it for P(0,0). Your (McKay) proof only does half of this (the P(n,m) => P(n, m+1) part) and that's why the version currently there is "longer". Moreover in the multiindex proof if you notice the bottom half of the proof where P(n,m) => P(n, m+1) is proved, it only takes up 5 lines as opposed to 6 (your version) and the lines are about half the length.

Using a double induction when an ordinary simple induction suffices is overkill and only serves to add unnecessary complication. P(n,1) together with P(n,m) => P(n,m+1) covers all m and n. The case P(n,1) is trivially true: there is only one term in the sum no matter what n is. There is no reason to use induction on n as well. It is also wrong to use unfamiliar notation when notation that everyone understands is perfectly adaquate. McKay (talk) 04:00, 17 November 2008 (UTC)
I'll concede the need for use for double induction. But doesn't the massive simplification of the proof using multiindex notation warrant its use? How is the use of multiindex not warranted but the use of sigma notation, and combination notation (which not 'everyone' understands) is? Clearly the audience of the page and specifically, the proof, is either familiar with multiindex notation or can familiarize him/herself in a manner of minutes. —Preceding unsigned comment added by RobotMacheen (talkcontribs) 00:04, 18 November 2008 (UTC)
It isn't a massive simplification at all, it is only a cosmetic change. The complexity of a proof doesn't depend on the number of symbols in it, but on the number of logical steps. As for the multiindex notation, it is very nice but not even most professional combinatorialists use it all the time (I'm speaking as an editor of combinatorics journals). Most mathematics graduates do not meet it at all during their studies. We shouldn't ask casual visitors to figure it out just to understand a very simple proof. McKay (talk) 00:26, 18 November 2008 (UTC)
I know this is a bit late, but for what it's worth I (as someone with at best a passing interest in combinatorics) find the multi-index notation useful, natural, and very easy to pick up. For someone who can follow the proof in the first place, I doubt asking them to learn that notation is too onerous. It's also convenient in other contexts, eg. in differential forms. In short, I would not be sad for it to become a mainstream notation. Unfortunately in this case, I suppose Wikipedia would like to reflect current practice, so the current proof should probably stay. 24.220.188.43 (talk) 09:45, 18 October 2011 (UTC)
Perhaps it deserves an article of its own, with some nice examples.McKay (talk) 06:56, 19 October 2011 (UTC)

### proof 1

$(x_1+x_2+\cdots+x_m+x_{m+1})^n = (x_1+x_2+\cdots+(x_m+x_{m+1}))^n$
$= \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$

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

$= \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}}$
$= \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}}$

which completes the induction. The last step follows because

${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}},$

as can easily be seen by writing the three coefficients using factorials as follows:

$\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}!}$

### proof 2

Now perform the inductive step for m and fixed n. For m = 1, both sides equal $x_1^n$. Similar to before, we suppose the multinomial theorem holds for m and fixed n. Then

$(x_1+x_2+\cdots+x_m+x_{m+1})^n = ((x_1+x_2+\cdots+x_m)+(x_{m+1})))^n$

Applying binomial theorem to the two terms inside the parentheses to get

$= \sum_{j=1}^n{n \choose j}(x_1+\cdots+x_m)^{n-j}x_{m+1}^j$

Then we apply the multinomial theorem for an exponent of n-j and rearrange

$= \sum_{j=1}^n\sum_{|\alpha|=n-j}{n \choose j}{n-j \choose \alpha}x^{\alpha}x_{m+1}^j$.
$= \sum_{j=1}^n\sum_{|\alpha|=n-j}\frac{n!}{j! \alpha_1!\cdots\alpha_m!}x_1^{\alpha_1} \cdots x_m^{\alpha_m} x_{m+1}^j$

So now we can define $\beta=(\alpha, j)$, i.e. $\beta_{m+1}=j$ and $|\beta| = j +|\alpha| =j + n - j = n$. With this, the above sum simplifies to

$(x_1+\cdots+x_{m+1})^n = \sum_{|\beta|=n}{n \choose \beta}x^{\beta}$

for $\beta = (\beta_1,\cdots,\beta_{m+1})$, thus concluding our proof of the theorem.

RobotMacheen (talk) 15:05, 16 November 2008 (UTC)

See binomial theorem, though. It has to be

(x + y + ... + t)n

expanded with multinomial coefficients.

Charles Matthews 15:58, 15 Apr 2004 (UTC)

## Commas appropriate?

I am used to seeing and writing the multinomial coefficient without commas,

${n \choose k_1 \; k_2 \; \ldots \; k_m}$

rather than with commas,

${n \choose k_1, k_2, \ldots, k_m} \,.$

Should we delete the commas from the article? Quantling (talk) 17:27, 25 June 2010 (UTC)

I see that the United States National Institute of Standards and Technology uses commas, e.g., here. I guess we should keep the commas. Quantling (talk) 19:49, 30 August 2010 (UTC)

## Multinomial coefficient definition

Speaking as a mathematician who has previously seen neither the multinomial theorem nor the multinomial coefficient, I found the beginning of the Theorem section very confusing. I subsequently hunted all over Wikipedia and some other web sites to find an explanation of the notation for the multinomial coefficient, only to finally find it defined further down in this article! The Theorem section needed some immediate explanation of what is in the formula. Consequently I inserted a brief definition of the multinomial coefficient immediately after the first appearance of the formula, refering to the more thorough description below it. I also re-worded some of the text to make the section easier to understand. Other than that, the section was easy to follow and understand, but a first-time reader should not have to already understand a concept before reading about it. — Anita5192 (talk) 07:00, 9 November 2011 (UTC)

Joel, I like the way you subsequently cleaned up parts of this article. I think this is much more readable now. Nice work! — Anita5192 (talk) 02:50, 23 November 2011 (UTC)
Thanks -- I thought your comments were a helpful guide (and the change you made was certainly necessary). --Joel B. Lewis (talk) 03:13, 23 November 2011 (UTC)