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.

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. RobotMacheen (talk) 14:45, 16 November 2008 (UTC)

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 (talk • contribs) 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}!}}$

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

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)

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)

Duh...? Just like that? Created by one stroke of His magic?

This article appears to be a one-snap creation of the You Know Who. It appears more as hallowed scriptures than mathematics, which is usually built painstakingly. By many. Like the Binomial Theorem. Bit by bit. From 300 odd BC to 1675 AD. Over many centuries. Okay. Now that I have your attention, I Apologise for this sudden interruption.🙏 :-) Just wanted to grab attention. Actually, I am not conversant with the history of multinomials, multinomial distribution and their development. Would be glad to have some inputs. Please🙏. Could we be helped? Us perpetual learners? Who savour history? Bkpsusmitaa (talk) 17:29, 7 November 2018 (UTC)

As in my edit summaries: huh? –Deacon Vorbis (carbon • videos) 17:51, 7 November 2018 (UTC)

@Deacon Vorbis: Didn't get you :-) Is it humour? Satire? I am totally caught off-guard. Apologise for my inability to catch the subtle flavour.

BTW, I forgot to mention that the article is very neat. Please accept my admiration.Bkpsusmitaa (talk) 18:00, 7 November 2018 (UTC)

Your comments appear incomprehensible and not obviously related to editing the article, which is the purpose of this page. If you would like to ask questions about mathematics, one local venue is WP:RD/MA. --JBL (talk) 20:00, 7 November 2018 (UTC)

Did they? Very well, I shall try to elaborate. Please look at the article, Binomial Theorem. Also look at the part Binomial_theorem#History. I believe that by perusing the links I have just provided you shall get to know the reason for my comments. Also, that they are actually concerned about more relevant inputs, and thus, editing.
I wasn't asking questions about mathematics. I was just trying to present what general readers of this article would be intrigued about, i.e., observing by stepping into readers' shoes. Bkpsusmitaa (talk) 15:51, 8 November 2018 (UTC)

If you would like to make a suggestion of an improvement, you are welcome to do so. (Even better, you could make the improvement to the article yourself.) --JBL (talk) 17:58, 8 November 2018 (UTC)

If I'm reading the intended implication correctly, the concern is a lack of discussion in the article of historical development of the theorem. In that case, by all means feel free to add history with relevant sources. JoshuaZ (talk) 02:47, 10 November 2018 (UTC)

First of all, don't know how to address you. Like Prof./Dr./Mr./Esq. and so on. So decided it was better that your initials / usernames were used. Please apologise the apparent lack of manners.
@JoshuaZ: Yes, that truly was what was intended. Thank you for your understanding and support.
@JBL: What JoshuaZ said above was truly what was intended to be put across to the original author. Would really have liked to add a section on the history of Multinomial Theorem. The cue is in the present article itself: "It is the generalization of the binomial theorem to polynomials." Which means the multinomial theorem was developed after the Binomial Theorem. Which is, after Issac Newton. Only that much. But by whom?
Don't have world-class accessible national public libraries with very old texts. Have nearly only WP :-) The Imperial Library or the Library of Congress would have helped a great deal. But, alas!
May be, the individual(s) who substantially wrote the history of Binomial Theorem here in WP could help? Such as AxelBoldt, Michael_Hardy, et al.
@AxelBoldt and @Michael_Hardy, could you please help?
Bkpsusmitaa (talk) 12:01, 9 December 2018 (UTC)

Multinomial Theorem of 2ⁿᵈ kind

Theorem : The number of non-negative integral solution of the equation $x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{k}=n$ is ${n+k-1 \choose k-1}$ Proof : Let $Equation-1:=x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{k}=n$ Let $f(y_{1},y_{2},y_{3},\cdot \cdot \cdot ,y_{k})=(y_{1}+y_{2}+y_{3}+\cdot \cdot \cdot +y_{k})^{n}$ ∴ Each term of $f(y_{1},y_{2},y_{3},\cdot \cdot \cdot ,y_{k})$ will be of the form $\displaystyle \sum _{x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{k}=n}{{\frac {n!}{x_{1}!x_{2}!x_{3}!\cdot \cdot \cdot x_{k}!}}\ y_{1}^{x_{1}}}y_{2}^{x_{2}}y_{3}^{x_{3}}\cdot \cdot \cdot y_{k}^{x_{k}}=\displaystyle \sum _{Equation-1}{{\frac {n!}{x_{1}!x_{2}!x_{3}!\cdot \cdot \cdot x_{k}!}}\ y_{1}^{x_{1}}}y_{2}^{x_{2}}y_{3}^{x_{3}}\cdot \cdot \cdot y_{k}^{x_{k}}$ $Where\ x_{i}\geq 0\ for\ all\ i\in [0,k]$

1. For each unique non-negative solution of Equation-1, there exist a unique monomial term of degree n of $(y_{1}+y_{2}+y_{3}+\cdot \cdot \cdot +y_{k})^{n}$.
2. For each unique monomial term of $(y_{1}+y_{2}+y_{3}+\cdot \cdot \cdot +y_{k})^{n}$, there exists an unique non-negative solution of Equation-1
3. No unique non-negative solution of Equation-1 yields two different monomial terms of $(y_{1}+y_{2}+y_{3}+\cdot \cdot \cdot +y_{k})^{n}$.
4. No unique monomial term of $(y_{1}+y_{2}+y_{3}+\cdot \cdot \cdot +y_{k})^{n}$ yields two different non-negative solution of Equation-1.

Thus, by bijection , $\#terms\ of\ g(x)=\#non-negative\ integral\ solutions\ of\ Equation-1$

Thus, to prove the theorem, it is sufficient to prove that number of terms of $f(x)$ is ${n+k-1 \choose k-1}$

Now, we shall proceed by Mathematical Induction.

• Base Case: $(y_{1}+y_{2}+y_{3}+\cdot \cdot \cdot +y_{k})^{n}$ for k=1 is $(y_{1})^{n}=y_{1}^{n}$, which has $1={n+1-1 \choose 1-1}\ terms$ terms.

Also, for k=2, $(y_{1}+y_{2}+y_{3}+\cdot \cdot \cdot +y_{k})^{n}$ is $(x_{1}+x_{2})^{n}=\displaystyle \sum _{i=0}^{n}{{n \choose i}x^{i}y^{n-i}}$, which has $\displaystyle \sum _{i=0}^{n}1\ terms\ of\ the\ form\ {n \choose i}x^{i}y^{n-i}$. $\displaystyle \sum _{i=0}^{n}1=(n+1)={n+2-1 \choose 2-1}$

• Induction Hypothesis: Let for some $k=r$, $(x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{r})^{n}\ \ has\ {n+r-1 \choose r-1}\ terms$
• Inductive Step: We have to prove that for $k=r+1$ too, $(x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{r+1})^{n}\ \ has\ {n+(r+1)-1 \choose (r+1)-1}\ terms,\ i.e.\ {n+r \choose r}\ terms$

$(x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{r+1})^{n}=\left[(x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{r})+(x_{r+1})\right]^{n}=\displaystyle \sum _{i=0}^{n}{{n \choose i}(x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{r})^{i}y^{n-i}}$ $For\ each\ unique\ i,\ {n \choose i}(x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{r})^{i}x^{n-1}\ has\ {i+r-1 \choose r-1}\ unique\ terms.\left[From\ Induction\ Hypothesis\right]$ Thus, $Number\ of\ terms\ of\ (x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{r+1})^{n}=\displaystyle \sum _{i=0}^{n}{{n \choose i}(x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{r})^{i}y^{n-i}}\ is\ \displaystyle \sum _{i=0}^{n}{i+r-1 \choose r-1}\ terms.$ ${\begin{aligned}\displaystyle \sum _{i=0}^{n}{i+r-1 \choose r-1}={r-1 \choose r-1}+{r \choose r-1}+{r+1 \choose r-1}+{r+2 \choose r-1}+\cdot \cdot \cdot \\+{n+r-2 \choose r-1}+{n+r-1 \choose r-1}=\left[{r \choose r}+{r \choose r-1}\right]+{r+1 \choose r-1}+{r+2 \choose r-1}+\cdot \cdot \cdot \\+{n+r-2 \choose r-1}+{n+r-1 \choose r-1}=\left[{r+1 \choose r}+{r+1 \choose r-1}\right]+{r+2 \choose r-1}+\cdot \cdot \cdot \\+{n+r-2 \choose r-1}+{n+r-1 \choose r-1}=\cdot \cdot \cdot \\=\left[{n+r-2 \choose r}+{n+r-2 \choose r-1}\right]+{n+r-1 \choose r-1}={n+r-1 \choose r}+{n+r-1 \choose r-1}={n+r \choose r}\ \left[Thus,\ proved\right]\end{aligned}}$

This is a theorem about the multichoose function, not about multinomial coefficients. It is covered in our articles on multisets and stars and bars (combinatorics). --JBL (talk) 18:42, 2 December 2020 (UTC)