Intuitive meaning for multinomial coefficient. (Why only one?)

Question

Introduction

I am doing a (university) probability course, wherein there seem to be occasional errors in what is taught. [Edit: this is not just my opinion.]

Background

I understand that the maths is the same for picking CEG from a collection ABCDEFGHIJ, as for tossing ttHtHtHttt — provided of course, that this is nCr and not nPr; nPr would count CEG, GCE, ECG etc. as different outcomes, which would not correspond with coin tossing. This is called “binomial coefficient”, for reasons that I understand somewhat.

Body

We have just been taught “multinomial coefficient”. C * (n1! * n2! * … * nr!) = n!.

It seems to be popular, in this area, to talk about allocating n items into r bins of sizes n1, n2 etc. . (It seems to me that) this is conceptually the same as allocating n items into n spaces, without worrying about the bins; it comes out as n! possibilities. That is wrong; C ≠ n!. [Edit/note: as I said below, I am open to correction on this.] (By “popular”, I mean that universities teach it and write it in their web sites, and there is no hint of any disagreement.)
———Edit02: I quote Wikipedia — citing the National Institute of Standards and Technology: “The multinomial coefficients have a direct combinatorial interpretation, as the number of ways of depositing n distinct objects into m distinct bins, with k1 objects in the first bin, k2 objects in the second bin, and so on.”
In turn, the latter says as follows.
“[MC formula] is the number of ways of placing n=n1+n2+⋯+nk distinct objects into k labeled boxes so that there are nj objects in the jth box.”
I think people generally think that an explanation is good, if • they already understand the pertinent concept and • the given explanation is consistent with the correct understanding.
The cold, hard fact — and [I tire of saying this] I am open to correction — is that, if one follows the directions on the packet, one gets n!.
Certainly, if one already knows that it is supposed to be a combination, and thus that one is supposed to DO AN EXTRA STEP OF removing all the duplicates, then sure, it is not inconsistent with a correct understanding.
If, conversely, one expects the National Institute of Standards and Technology to be able to give a proper account of a concept… then, again, if one does what they say, one ends up with n! permutations.
(Wikipedia I expect to be able to give an account that is intelligible only to people who do not need one.)
THE NUMBER OF WAYS OF PLACING N DISTINCT OBJECTS INTO N SPACES IS N!.
(If that is wrong, then maybe you should take down Wikipedia and the National Institute of Standards and Technology (not to mention a bunch of universities), rather than picking on me.)
———End Edit02.

Actually, (apparently) it parallels “binomial coefficient”. One question, then, is that of why we do not have one coefficient for each bin… and thus what this single coefficient means.

———Rant (now that I am getting a handle on it)
I wonder, briefly, whether the idea is that
C(n1!,n1!) * C(n2!,n2!) * … * C(nr!,nr!) = n! / (n1! * n2! * … * nr!).
If it does, I wonder why no one is saying this.
If it does, the C is left out. Perhaps the idea is that
C(n1!,n1!) * C(n1!,n1!) * … * C(nr!,nr!) = C * (n1! * n2! * … * nr!) = n!. (Or maybe
P(n1!,n1!) * P(n1!,n1!) * … * P(nr!,nr!) = C * (n1! * n2! * … * nr!) = n!.)
In that case, it seems that C represents the value of the sad fact that the two are not equal… and I still wonder why no one is saying it… and I still wonder what the C means, intuitively.
———End Rant

———Begin Commented (Edit02)
Incidentally, the concept taught in my course is that this is about allocating n items into bins, as above. …Except with a difference. In the example given, there are 3 bins, of sizes 2, 3 and 4. The value for the first bin is 2P2 = 2! = 2. The value for the second bin is 3P3 = 6. The value for the third bin is 4P4 = 24. (I have no idea why [i.e. how they justify allocating 2 items from a collection of 9], except that it looks good.) It turns out that there is a subtle error in the result of this. It looks perfectly meaningful — you got yur 2P2, and yur 3P3 and yur 4P4; waddayawaan?. I call the above C' (“C prime”, I think that is called). C * C' = n!. I’ll say that again. C * C' = n!.
———End Commented: Now that I understand the concept correctly… the pertinent person appears to understand the concept correctly, and the exercise answer is correct — contrary to the foregoing objection. I maintain that the account given in the lecture, of the concept, does not qualify as a decent explanation for an audience that does not know it… and indeed (I consider) is objectively not quite right. Independently of that… I strongly maintain that a minimally decent explanation of MC should state whether the individual bin possibilities are a permutation or a combination.
(For myself… it is a tremendous relief, in terms of mental effort, to establish that there is no conflation of $C$ and $C'$ going on out there.)

I am getting tired of reading [edit: putatively] false accounts of what C is and means. (Actually, I have not found any account of what C means, intuitively. (I suspect that no one has any idea (except false ones, of course).) … … Edit: I am thinking/wondering whether [as below] this is because any given C is not a concept on its own — only as part of its set (?).)

Any help would be appreciated.

Thank you in advance, and best wishes to you.

p.s. I am comfortable with anyone explaining that the {n items into bins} idea does not equal n!, or that it is I who has missed something subtle in the C' thing.

————
Edit. Thank you hugely, everyone; I really appreciate it.
I am realising [rightly or wrongly!] that, in the same way as there is a set of binomial coefficients for, for instance, 5 (being 5C1, 5C2, 5C3, 5C4, 5C5)… so there is a set of multinomial coefficients for (I take it) {any given n! and its “bins”}… except that there are a lot more of them.
Sorry about my tone; it is just that it is really hard to try to learn something and concurrently figure out whether or not it is correct.

Edit02    The answer — short version

• My way of doing it [now that I know what a MC is (and as a possibility, before then)] is to do a full permutation set, in the $n$ spaces, and then reduce each bin to a combination. This yields the formula directly (being $n!$ / ($n_1$ etc.) ).
• Apparently everyone else understands the concept… in terms of doing it by stages. This is where the standard long formula comes from, that must then be algebraically massaged into the standard form.

I think part of the problem for me has been that, if everyone rejects the direct, simple way, that leads directly to the right formulation… I don’t know; one assumes very strongly that people would not do that.

Answer 1

The binomial coefficient $\binom{n}k$ is the number of subsets of the set $\{1,2,\ldots,n\}$ of size $k$. For example, $\binom42=6$, because there are $6$ $2$-element subsets of $\{1,2,3,4\}$; they are $\{1,2\}$, $\{1,3\}$, $\{1,4\}$, $\{2,3\}$, $\{2,4\}$, and $\{3,4\}$. If you think about this a bit, you should be able to see that $\binom{n}k$ is also the number of ways to distribute the members of the set $\{1,2,\ldots,n\}$ between two numbered bins in such a way that Bin $1$ gets $k$ members of the set: Bin $2$ simply gets the $n-k$ members of the set that were not chosen to be part of the $k$-element set.

The multinomial coefficient $\binom{n}{k_1,k_2,\ldots,k_r}$, where $k_1+k_2+\ldots+k_r=n$, generalizes this idea: it is the number of ways to distribute the members of the set $\{1,2,\ldots,n\}$ amongst $r$ numbered bins in such a way that Bin $i$ gets $k_i$ members of the set for $i=1,2,\ldots,r$. There are, for instance, $\binom{5}{3,1,1}$ ways to distribute the integers $1$ through $5$ amongst three numbered bins so that Bin $1$ gets $3$ of them and Bins $2$ and $3$ get just one each. It is possible, if a little tedious, to list all $20$ of these distributions:

$$\begin{array}{c|c|c} \text{Bin }1&\text{Bin }2&\text{Bin }3\\\hline 1,2,3&4&5\\ 1,2,3&5&4\\ 1,2,4&3&5\\ 1,2,4&5&3\\ 1,2,5&3&4\\ 1,2,5&4&3\\ 1,3,4&2&5\\ 1,3,4&5&2\\ 1,3,5&2&4\\ 1,3,5&4&2\\ 1,4,5&2&3\\ 1,4,5&3&2\\ 2,3,4&1&5\\ 2,3,4&5&1\\ 2,3,5&1&4\\ 2,3,5&4&1\\ 2,4,5&1&3\\ 2,4,5&3&1\\ 3,4,5&1&2\\ 3,4,5&2&1 \end{array}$$

This is quite different from the $5!=120$ ways of distributing the same integers amongst $5$ numbered bins, i.e., of lining them up in some order. We could of course start by lining them up, then put the first three integers into Bin $1$, the fourth integer into Bin $2$, and the fifth integer into Bin $3$, but then $3!=6$ permutations (line-ups) would correspond to the same distribution into our three bins: the permutations $12345$, $13245$, $21345$, $23145$, $31245$, and $32145$ would all yield the first distribution in the table above.

The multinomial coefficient can, however, be calculated directly from binomial coefficients, because there the task of distributing the members of the set $\{1,2,\ldots,n\}$ amongst $r$ numbered bins in such a way that Bin $i$ gets $k_i$ of the numbers can be broken down into sequence of $r$ subtasks, each of which consists of choosing a certain number of elements from a set. First, there are $\binom{n}{k_1}$ different $k_1$-element subsets of $\{1,2,\ldots,n\}$, so there are $\binom{n}{k_1}$ ways to choose the contents of Bin $1$. Once that is done, $n-k_1$ numbers remain to be distributed, and there are $\binom{n-k_1}{k_2}$ ways to choose $k_2$ of them for Bin $2$. Continuing in this fashion, we find that there are

$$\binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\ldots\binom{k_{r-1}+k_r}{k_{r-1}}\binom{k_r}{k_r}\tag{1}$$

ways to perform this sequence of selections and hence to fill the $r$ bins with the required number of elements of $\{1,2,\ldots,n\}$. One can therefore view the multinomial coefficient $\binom{n}{k_1,k_2,\ldots,k_r}$ as an abbreviation for the product $(1)$ of binomial coefficents. And if one then rewrites the binomial coefficients in terms of factorials, one finds that a great many of the factorials cancel out, leaving just

$$\binom{n}{k_1,k_2,\ldots,k_r}=\frac{n!}{k_1!k_2!\ldots k_r!}\;.$$

For example,

$$\begin{align*} \binom{10}{3,5,2}&=\binom{10}3\binom{10-3}5\binom{10-3-5}2\\ &=\binom{10}3\binom75\binom22\\ &=\frac{10!}{3!\color{red}{7!}}\cdot\frac{\color{red}{7!}}{5!\color{blue}{2!}}\cdot\frac{\color{blue}{2!}}{2!0!}\\ &=\frac{10!}{3!5!2!0!}\\ &=\frac{10!}{3!5!2!}\;. \end{align*}$$

In conclusion I’ll say that I very much doubt that you’ve read many (if any) false accounts of the meaning of binomial and multinomial coefficients. These coefficients turn out to have a multitude of applications and interpretations (‘meanings’), and all of those interpretations are correct in the appropriate settings. What I’ve described here is probably the simplest and most basic interpretation, but it is far from being the only one.

Answer 2

That was a huge wall of text... I can't help but ignore more than half of what you have written.

Instead, I will try to explain again what a multinomial coefficient is and one of the ways you can derive the formula for it.

To start, I will assume you have already been exposed to the binomial coefficient, what I will notate as $\binom{n}{r}$ and what can be proven to be equal to $\dfrac{n!}{r!(n-r)!}$. The binomial coefficient answers many counting questions and algebraic questions, one of which may have been taken as the motivating definition for the binomial coefficient which varies depending on where you learned from, among which would include such things as

• $\binom{n}{r}$ is the coefficient of the $x^ry^{n-r}$ term in the expansion of the binomial $(x+y)^n$

• $\binom{n}{r}$ is the number of subsets of size $r$ from a set of size $n$

• $\binom{n}{r}$ is the number of binary sequences of length $n$ with exactly $r$ 0's (and thus $n-r$ 1's)

• $\binom{n}{r}$ is the number of lattice paths along a unit square grid from $(0,0)$ to $(r,n-r)$ traveling using movements of exactly one unit to the right or exactly one unit up at a time.

• $\vdots$

---

Now... multinomial coefficients answer very similar questions. I will notate multinomial coefficients as $\binom{N}{n_1,n_2,n_3,\dots,n_k}$ where we require that $n_1+n_2+\dots+n_k=N$. One can prove that the multinomial coefficient is algebraically equivalent to $\dfrac{N!}{n_1!n_2!n_3!\cdots n_k!}$. Note, the special case of $k=2$, we have the multinomial coefficient is exactly the same as the binomial coefficient.

• $\binom{N}{n_1,n_2,\dots,n_k}$ is the coefficient of $x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k}$ in the expansion of $(x_1+x_2+\dots+x_k)^N$

• $\binom{N}{n_1,n_2,\dots,n_k}$ is the number of ways to partition a set of $N$ objects into $k$ labeled disjoint subsets of sizes $n_1,n_2,\dots,n_k$ respectively

• $\binom{N}{n_1,n_2,\dots,n_k}$ is the number of $k$-ary sequences of length $N$ consisting of $n_1$ 0's, $n_2$ 1's, ... $n_i$ i-1's,... on up to $n_k$ k-1's. (Traditionally, k-ary sequences use the digits $\{0,1,2,\dots,k-1\}$, hence the shift. If you prefer, you can say instead $n_1$ copies of "the first character" and so on...)

• $\binom{N}{n_1,n_2,\dots,n_k}$ is the number of lattice paths in a $k$-dimensional hypergrid starting from point $(0,0,\dots,0)$ and ending at $(n_1,n_2,\dots,n_k)$ where we only travel in unit distances at a time in any of the positive axial directions

---

Proving that $\binom{N}{n_1,n_2,\dots,n_k} = \dfrac{N!}{n_1!n_2!\cdots n_k!}$ using binomial coefficients to do it:

Using the interpretation of $k$-ary sequences for convenience, let us break apart with multiplication principle and the following steps.

• Choose which $n_1$ of the $N$ available spaces are used for the digit 0. This can be done in $\binom{N}{n_1}$ ways.

• Choose which $n_2$ of the $N-n_1$ remaining available spaces are used for the digit 1. This can be done in $\binom{N-n_1}{n_2}$ ways.

• Choose which $n_3$ of the $N-n_1-n_2$ remaining available spaces are used for the digit 2. This can be done in $\binom{N-n_1-n_2}{n_3}$ ways.

• $\vdots$

• Finally the remaining $n_k$ spaces will be used for the digit k-1.

This shows that $\binom{N}{n_1,n_2,\dots,n_k}=\binom{N}{n_1}\cdot \binom{N-n_1}{n_2}\cdot \binom{N-n_1-n_2}{n_3}\cdots \binom{N-n_1-\cdots - n_{k-1}}{n_k}$

$=\dfrac{N!}{n_1!\color{red}{(N-n_1)!}}\cdot \dfrac{\color{red}{(N-n_1)!}}{n_2!\color{blue}{(N-n_1-n_2)!}}\cdot \dfrac{\color{blue}{(N-n_1-n_2)!}}{n_3!\color{green}{(N-n_1-n_2-n_3)!}}\cdots$

Now, notice all of the cancellation that can occur. This finally simplifies to:

$$\binom{N}{n_1,n_2,\dots,n_k} = \dfrac{N!}{n_1!n_2!\cdots n_k!}$$

Another popular approach might have been to use a "division by symmetry argument" which I like to avoid, but the punchline is that if we were to temporarily assume each of the digit $0$'s were distinct, there are $n_1!$ ways to rearrange them which would have been considered different but we don't want to consider different. For each of these, there are $n_2!$ ways to rearrange the 1's, and so on... leading to $n_1!n_2!\cdots n_k!$ rearrangements of the digits had they all been considered distinct for each arrangement we want to consider truly "different." Dividing by that overcount gives us the true count.