Multinomial Coefficient — the Derivation is Incoherent

Preface

Originally published on LinkedIn on 2020.05.16.

2020.06.05 — Update — Amongst the material that I have been using to figure out what the multinomial coefficient is, I have noticed a derivation that is like the one that I reject below (in generating the same long expression), but which begins with a different conceptualisation of the m.c., and which appears to thus make sense. In this case, it is still true that one can arrive directly at the final expression (i.e. without having to generate a huge mathematical expression and then simplify it). I still think that the derivation that I was taught originally was an attempt to express the concept that I have argued to be incoherent, but of course I shall now have to check that, in the light of this new aspect of the situation. Given that it was… there is the further question of whether that is just that one odd case, or whether that thinking is standard or typical. I am (as a result of the foregoing) still/again thinking through all this, so I have to leave until later the task of editing this article to incorporate this new information. Again… I still maintain that the huge mathematical expression is unnecessary (albeit now for both cases).

My purpose, in writing this, is twofold.  One purpose is to give another example of my claimed ability to see and solve problems that other people do not think exist.  The other purpose is to supply {a simple account of a concept} which (oddly enough) no one else appears to be able to see, for the benefit of anyone else who might be trying to understand it. 

I am thinking of expanding this into a fuller account of the binomial and multinomial coefficients, perhaps with some of the prior concepts also explained… but my purpose at this point is to get this published. 

p.s. “$” is a signal to Latex to start and to stop; Latex is a program that draws mathematical expressions properly. One learns to ignore them [the “$”s] after a while.  [For the uninitiated… .  • In Latex, “_” means “subscript [follows]”.  • Watch out for those “!”.  (“!” means “factorial”; for instance “4!” means 4*3*2*1.)  • The number of possible permutations of n=5 items in r=5 spaces is 5*4*3*2*1, since you can not re-use items.  The number of possible permutations of n=8 items in r=5 spaces is 8*7*6*5*4; the simplest way to write this is 8!/3! = n! / (n-r)! ; this gets rid of the 3*2*1.] 

Body

I have recently been doing a course in probability.  There was a lecture explaining the concept “multinomial coefficient”.  To cut a long story short, it turns out that the standard account of how to derive the pertinent formula is incoherent. [See the “update” above.]

Another difficulty I had, in understanding this concept, is that there is a perfectly straightforward account of this concept — my understanding of it, so to speak — that leads directly to the final formula (which the standard account gets to via some rather tedious simplifying)… and I can not find this stated anywhere.  (The reason that that is a difficulty is that one imagines that, given that a simple, direct account of a concept existed… [that] people would use it… from which one infers that said simple, direct account must be wrong.) 

I shall present the latter [“my way”] below, and then run through the former [“the standard way”], showing the incoherence. 

Firstly, though… the third main difficulty for a learner trying to apprehend this concept is that the standard (simple conceptual) description of the concept is wrong.  [I am open to correction on this, but it seems that that simply would not happen, regardless of whether I am right or wrong, because [it seems that] (other) people are quite unable to even *think* about the *idea* of anything widely accepted being wrong — from {some stupid idea some student had} all the way up to a famous scientist claiming that the Earth revolves around the Sun or that disease is caused by invisible germs.]  [I shall give a (correct) description of the concept shortly.] 

The standard (simple conceptual) description of the concept is as follows.  Here, I am quoting Wikipedia (2020.05.11-ish) [which is not an endorsement], which cites the National Institute of Standards and Technology [which linked article I checked].  The multinomial coefficient is, “… 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.”  The pivotal point here is that the mention of bins is not doing any (described) work.  If they went on to explain that that (as described) is simply nPn, and include the crucial point that the multinomial coefficient is about combinations, not permutations, or mention subsets… within each bin… that would be a description of the multinomial coefficient. …But they do not.  It is wrong.  The number of ways of “depositing” n distinct objects is the number of possible permutations [as opposed to a multinomial coefficient].  Indeed, that is pretty good as a definition of permutation.  It is just wrong.  Just mentioning that there are “bins” does not change this.  [Again… the bins are not doing any work; the m.c. counts the number of subsets in each bin, rather than the “number of ways of depositing n distinct objects…”.]  I suggest that it does appear that people think it does.  I note further that the concept of multinomial coefficient is about combination, as opposed to permutation… which the difference being, particularly, *eliminating* {different “ways of depositing” the same items} from the count. 

The following is a (correct) definition of the Multinomial Coefficient.  [This is not intended as a fully perfect, quotable definition.  Indeed, understanding the below “My Way” derivation renders the formula itself the most compact expression of the concept.] 

“Given a full count of possible permutations of $n$ items into $n$ spaces… and given that these spaces are categorised into $k$ bins… the multinomial coefficient applies a reduction of each bin count from a set of permutations to a set of combinations. That is, conversely…barring duplication across bins — it is a full count of all the possible combinations [as opposed to permutations] of the $n$ items in each of the $k$ bins… and (multiplicatively) across all of the $k$ bins.” 

(The following account of how to derive the multinomial coefficient [“My Way”] helps to explain this.) 

We shall come to the standard way of deriving the multinomial coefficient shortly [“The Standard Way”, below].  First, the obvious and simple way. 

This obvious and simple way I have worked out for myself.  I expect anyone who reads this to respect my I.P. (except if it happens to be explained this way elsewhere already and I could not find it (although I do doubt that, unless there is some motive for people to suppress the simple, clear account)). 

My Way 

We are talking about n spaces, categorised into k bins of sizes $n_1$, $n_2$,… to $n_k$.  Towards generating a multinomial coefficient, we have n distinct items — the same number as the number of spaces. 

Herein, throughout, I shall use an example where • n=9, • the items are A B C D E F G H I, and • the first few bin sizes are 3, 2… and we do not care after that.  

Step 1 is to generate all the permutations of the n items into the n bins.  (We do this the usual way — hierarchically, working from left to right… for each space, we list every item in that space and, for each of these, subordinately we list all the items in the next space — excluding, for each individual case [permutation], any items that we have already used in this case [permutation].) 

Step 2 is to apply a reduction from a permutation to a combination… except that we do this bin by bin, rather than for the entire n spaces at once.  We are, of course, talking about listing all the possibilities (as opposed to talking about a given one).  For any set of spaces $p$, the reduction from a permutation to a combination is done by dividing by $p!$.  (Thus, for instance, 9P3 is 9! / (9-3!), and 9C3 is 9! / (9-3)! / 3! = 9! / [ (9-3)! * 3! ].)  (The reason for this is clear working backwards.  Any given [read “1”] set of $p$ items can be arranged in $p!$ ways in $p$ spaces.  Thus, every $p!$ different arrangements of items in $p$ spaces represents 1 unique set of items.) 

This leads directly to the result — n! / [ (n_1)! * (n_2)! * … * (n_k)! ].  That is… for each bin, we do the reduction by dividing by $n_i$ (using $i$ as a counter). 

That’s it; no additional maths.  The multinomial coefficient can be described as counting every possible combination of the bin-by-bin subsets, for the entire permutation list (across all the bins).  (A subset is a combination, not a permutation, because different orderings of a set of particular items represent the same subset.) 

This brings us to the standard way of deriving the multinomial coefficient (which I have claimed to be incoherent).  This is extrapolated from the way of deriving the number of permutations of items into spaces (which I described in Step 1, above). 

The Standard Way 

Edit 2023.09.14.   Possibly I might attempt a re-write of this [following] section, later.  (I did write it during [near the end of] the period in which I was concurrently • trying to learn the concept and • trying to work out what — if anything — was wrong with the account of it.)  At this point, I shall settle for adding the following explanatory point.
The issue has to do with the fact that  • the Permutation count is deduced by praxis — [thinking through] methodically trying each of the items in the first position (n instances), and… hierarchically and subordinately trying each of the available remaining items in the second position (subordinately (n-1) instances; n*(n-1) total instances so far) and so on… but  • the Combination count is deduced (from nPn) by theory — by the mathematical move of dividing by {the number of instances in which the same items are used in a different order}.
[ Note carefully that, during the process of doing the permutation count, every item is tried in every position (multiple times); the process is a clever trick that makes sure that the same item does not appear in more than one position, in any given counted instance.  (That is… it counts only those instances in which there are no duplicates.) ]
That is… the issue that I try to explain, in this [following] section is that the standard account of how to derive the M.C. invalidly intermingles those two constructs; during a methodical trying of items in positions, it applies a mathematical reduction… which invalidates the subsequent methodical {trying of items in positions}.

This way derives the overall multinomial coefficient step-by-step — the same way as a permutation of n items is derived — but its output then requires (arduous) mathematical simplifying.  The setup is the same as above — n items to be distributed among n spaces that are categorised into k bins. 

Step 1A.  We generate permutations of the n items, in the usual way, starting from the left… but we pause when we have filled the $n_1$ spaces in the first bin (i.e. filled bin 1).  At this point, our count is $n$P($n_1$). 

Step 1B. As above, we apply a reduction, from a permutation to a combination, for this bin — i.e. we divide the result by $n_1$… giving $n$C($n_1$) = $n!$ / [ ($n$-($n_1$)) * ($n_1$) ]. If, for example, there were 9 items (for 9 spaces), and the size of the first bin was 3, we would have, so far, 9C3 = 9! / [ 6! * 3! ]. 

We repeat Step 1 (i.e. Step 1A and Step 1B) iteratively, proceeding left to right, bin by bin. 

Thus, in the second iteration, we (A) fill the $n_2$ spaces in bin 2 in the usual way for a permutation list, and then (B) divide by $n_2$ to reduce this to a combination. 

… and there is a problem 

Edit 2023.09.14.   It seems that I got carried away with writing “!”s.  For instance, below I said that the possible permutations for the first bin (with 3 spaces) is “ $9! * 8! * 7!$ ”; I am thinking that should be just “ $9 * 8 * 7$ ”.  I have now made the appropriate corrections (I hope).

There is a problem here.  We want to ultimately count all the possible permutations for the entire set of n spaces.  The reason that this is a problem is that generating the permutations bin by bin — *pertinently* — is an incoherent concept (as follows). 

For the case of 9 items in 9 spaces… we list the 9 items in the first space; under each of these, separately, we list the remaining 8 items; under each of these, separately, we list the remaining 7 items; under each of these, separately, we list the remaining 6 items… and so on. 

Counting the possible permutations for a first bin with 3 spaces is fine; we simply stop when we have listed those $9 * 8 * 7$ possibilities. 

The problem for the second bin is that, if we are counting all the possible permutations (of n=9 items) for the entire set of n=9 spaces — and if there are 3 spaces in bin 1 — we have $9 * 8 * 7$ instances of bin 2 to consider.  [See also below.]  The popular claim is that – in this example — there are 6P2 possible permutations in bin 2.  Consider, however… which 6 items are we restricting ourselves to?  Can we use A?  Yes.  Can we use B?  Yes.  Can we use C?  Yes.  Can we use D?  Yes.  Can we use E?  Yes.  Can we use F?  Yes.  Can we use G?  Yes.  Can we use H?  Yes.  Can we use I?  Yes.  That is 9 items — the full set.  What is going on? 

If we are doing a full list of all the permutations for the entire set of n=9 spaces… then, if we interrupt the process, and consider 1 instance of bin 2 — 1 of the $9 * 8 * 7$ instances that we will ultimately have overall — then it is indeed true that, at this point in the overall process, there are 6P2 possible permutations for bin 2… since, at this specific point in the overall process, there are 3 particular items that are excluded — the 3 in the first 3 spaces. These might be FBG or IAE or ABC… any one of the $9 * 8 * 7$ possibilities.  If we interrupt somewhere else, the first 3 items might be CHF or IBG or EDH… again, there are $9 * 8 * 7$ possibilities there… and again there are 6P2 possible permutations for this instance of bin 2.  Note that this is now a different instance of 6P2 possible permutations. 

In isolation, the correct number of possible permutations for bin 2 is 9P2 = $9 * 8$ — 2 spaces for 9 available distinct items.  Again… however we position everything… all n=9 items are legitimate for the first space in bin 2.  This would be the correct amount if we were to do bin 2 as a genuinely separate step. 

If, conversely to the above, we consider all $9 * 8 * 7$ instances of bin 2 — with each of these representing 6P2 = $6 * 5$ possible permutations — then obviously we shall have more than $9 * 8$ cases — $9 * 8 * 7 * 6 * 5$, actually.  It is not difficult to see that there will be duplicates; in the first bin we are doing permutations, so any set of 3 items there will be repeated ($n_1$)! = 3! times. 

Actually, we already divided by ($n_1$)! = 3! in the previous step.  This compensated mathematically for those duplicates.  By the same token, since those $9 * 8 * 7$ permutations include different permutations of the same items, there will be fewer instances of bin 2 in this (second) iteration — hypothetically.  Actually, all we did was divide by ($n_1$)! = 3!; we did not actually eliminate actual duplicates of actual items.  Thus, to get the various possible permutations in bin 2 correct, we still have to run through the full $9 * 8 * 7$ instances of it… because (again) we have not actually systematically eliminated actual duplicate sets of actual items. 

It seems, then, that we have 6P2 = $6*5$, 9P2 = $9*8$ and 9P5 = $9*8*7*6*5$… and $9*8*7*6*5 / 3!$… vying for the title of correct answer for bin 2.  We know that 6P2 is correct, in that that is the value here that gives the correct answer.  Unfortunately, this seems to be the only value for which we have no justification at all.  As I have shown, if we are following the “Standard Way”, then either • we have $9 * 8 * 7$ instances of that bin to account for — with this including many duplicates (but not such that removing these duplicates resolves the difficulty (neither mathematically nor actually))… or • it appears that the value for bin 2 should be $9 * 8$. 

In simple English… you can not do bin 1 and then do bin 2; you have to do bin 2 while (and subordinately to) doing bin 1.  If you actually do count all the possible permutations of n items in bin 1, and all the possible permutations of n items in bin 2, and so on — which (again) is what the “Standard Way” says to do… well, you are not going to get the multinomial coefficient, unless you do some further shenanigans to recover the concept.  Further (in simple English), doing bin 2 while (and subordinately to) doing bin 1 does not allow you to treat bin 2 as separate. 

The resolution of this difficulty is to concede that the “Standard Way” account is incoherent.  In respect of counting the permutations… 9P5 = $9 * 8 * 7 * 6 * 5$ is the correct answer for bins 1 and 2 *combined* — that is, the value that our ongoing count will have reached when we have completed the counting for bins 1 and 2.  There is no coherent way to conceptually detach bin 2.  [Again, dividing by $n_1$ to reduce the permutation to a combination does not resolve this problem (and is incoherent).] 

There is a good reason for that.  The multinomial coefficient is based on nPn — the permutation of n items into n spaces.  Permutations of these n items into smaller bins represent irrelevant and inapplicable concepts.  The only reason the move looks at all plausible is that it corresponds for the first bin — only the first bin, that is.  Similarly, it corresponds for bins 1 and 2 *combined*, and for bins 1, 2 and 3 *combined*, and so on.  It will keep corresponding as long as we keep discarding any concept of separate bins as we proceed. 

The maths putatively works for the “Standard Way” — and the “Standard Way” itself appears to work — only because it is possible to forget the formal process that one is following, for deriving the multinomial coefficient — with bins that are actually doing relevant work — which is easy when said process is incoherent — and imagine instead that one is working through the clean and simple process for deriving nPn for the whole n spaces — which (again) has no “bins” concept.