0
$\begingroup$

This counting problem came up while thinking about a statistical mechanics problem. I've been able to reformulate the question to be as follows. Say we have three distinct objects of multiplicity $q$,$r$, and $s$ which are to be put into $N$ distinct boxes. Assume $q+r+s=N$. How many ways can this be done if each box can contain exactly one object? I've tried messing around with some simple examples and it gets terribly unwieldy. Perhaps there is no simple answer? I think it may be related to Sterling numbers of the second kind. If anyone has some intuition or references or a simple answer I would be greatly intrigued!

$\endgroup$
  • $\begingroup$ $\binom{N}{q,r,s}=\frac{N!}{q!r!s!}$, the multinomial coefficient seems to be what you are looking for. $\endgroup$ – JMoravitz Jun 5 '16 at 4:00
  • $\begingroup$ @JMoravitz if you want to type up a little answer with some interpretation I would accept it! Maybe relating the interpretation given on wiki to this particular problem $\endgroup$ – ClassicStyle Jun 5 '16 at 4:07
1
$\begingroup$

The multinomial coefficient $\binom{N}{q,r,s}=\frac{N!}{q!r!s!}$ is the number of ways to arrange objects of three kinds with $q$ indistinguishable objects of the first kind, $r$ indistinguishable objects of the second kind, and $s$ indistinguishable objects of the third kind in a row.

One of the common examples is counting the arrangements of the word "MISSISSIPPI"

There are $\binom{11}{4,4,2,1}$ arrangements.

In the same way, for your problem, we are essentially asking for how many arrangements of the word "$\underbrace{11\dots1}_{q}\underbrace{22\dots2}_r\underbrace{33\dots3}_s$" there are.

To derive the formula to begin with, one may temporarily assume that all balls of the first kind are in fact distinguishable, as well as each other kind. There are then $N!$ ways to distribute all balls such that each box receives exactly one ball. We realize then that we overcounted since we consider each arrangement where balls of a specific type are swapped to be the same. Dividing by $q!$ accounts for the overcounting caused by balls of the first kind. Similarly, dividing by $r!$ and $s!$ will fix the overcounting caused by the other kinds. This arrives at the answer $\frac{N!}{q!r!s!}$

An alternate way to arrive at the formula is by breaking apart via multiplication principle. First choose which boxes receive the balls of the first kind. $\binom{N}{q}$ options. Once this has occurred, from the remaining available boxes, pick $r$ of them to receive balls of the second kind. $\binom{N-q}{r}$ options. Finally, the remaining boxes will receive the balls of the third type.

This arrives at the answer of $\binom{N}{q}\binom{N-q}{r}\binom{N-q-r}{s}$ which after algebraic manipulation equals the same as before.

$\endgroup$
  • $\begingroup$ Awesome answer! Thank you $\endgroup$ – ClassicStyle Jun 5 '16 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.