1
$\begingroup$

I am having troubles understanding a combinatorics formula. I would appreciate any ideas or hints, leading to an explanation how this formula might be derived. I came across the formula reading a book on statistical physics. Unfortunately the formula was given without derivation.

Suppose a total number of objects $N$ and a set of '$m$' boxes are given. To each of these boxes, fraction $n_i$ of the $N$ objects might be assigned. With the condition that

$$ \sum_{i=1}^m n_i = N $$

According to my textbook the total number of ways to generate certain distribution $W\{n_i\}$ is given by

$$ W\{n_i\} = \frac{N!}{\prod_i n_i!}, $$

where $i$ runs over all boxes. I have troubles understanding how the formula for $W\{n_i\}$ is derived.

To make things more clear consider the case with four boxes, where

$$ N=5\\ n_1=2\\ n_2=2\\ n_3=1\\ n_4=0\\ $$

In this particular case one can generate the following distributions over the four boxes

$$ |1,2|3,4|5|0|\\ |1,3|2,5|4|0|\\ |2,5|1,4|3|0|\\ ...... $$

The textbook goes further and defines the total probability $W_{tot}\{n_i\}$ of finding the distribution $\{n_i\}$

$$ W\{n_i\} = N!\prod_i\frac{\omega_i^{n_i}}{ n_i!}. $$

Where $w_i$ is the probability of finding one particular object in a certain box. Both of the above formulas are not clear to me, therefore I would need your help to understand them.

Thank you for reading my question.

Best Regards,

Alex

$\endgroup$
  • $\begingroup$ In short, you're dealing with a multinomial distribution. $\endgroup$ – Graham Kemp May 20 '14 at 1:42
4
$\begingroup$

I have troubles understanding how the formula for $W\{n_i\}$ is derived.

It's just the multinomial coefficient. ${n\choose k_1,k_1,\ldots k_m} = \frac{n!}{k_1!k_2!\cdots k_m!}$

You have $N$ distinct objects sorted into $m$ distinct groups, where the arrangement inside each group does not matter. The number of objects within any group $i$ is $n_i$

There are $N!$ ways to rearrange $N$ distinct objects. There are $n_i!$ ways to rearrange all objects in box $i$. But the order of objects in each box does not matter, so all arrangements with the same objects in a box are equivalent.

Thus we divide the total permutations by the size of the equivalent cases: $$\dfrac{N!}{n_1!n_2!n_3!\cdots n_m!}=\dfrac{N!}{\prod\limits_{i=1}^m n_i!}$$


Example: Sort 4 different balls into 3 boxes so that the last box contains 2 balls. Let us count the ways.

There are $4!$ ways to arrange 4 different balls. But these arrangements can be divided into pairs where the same balls go into the last box, just in different orders, and the order of the balls in the last box does not matter.

So there are $\frac{4!}{1!1!2!}$ ways to sort the balls into these boxes.


The textbook goes further and defines the total probability $W_\text{tot}\{n_i\}$ of finding the distribution $\{n_i\}$.

And here we have a multinomial distribution. This is analogous to the binomial distribution::

$$X\sim\mathcal{B}(n,p) \iff \mathrm{P}(X=x)={n\choose x}p^x (1-p)^{n-x}$$

Which is the probability of $x$ successes in $n$ trials, with probability $p$ of an individual success.

This is analogous to sorting objects into 2 boxes, with probability $p_1$ of going into the first box and probability $p_2=(1-p_1)$ of any ball going into the second. So:

$$P(X_1=n_1, X_2=n_2 : n_1+n_2=N) = \frac{N!}{n_1!n_2!} p_1^{n_1}p_2^{n_2}$$

Now just extend this to the case of $m$ boxes.

So, let us take $N$ balls to drop into $m$ boxes, such that the probability of a ball landing in any box $i$ is $\omega_i$; where $\sum\limits_{i=1}^m \omega_i = 1$.

Now the probability that box $1$ contains $n_1$ balls, and box $2$ contains $n_2$ balls, and so on, and so on is: $$W_\text{tot}\{n_i\} \\ = P(X_1=n_1, X_2=n_2, \ldots, X_m=n_m) \\ = {N\choose n_1,n_2,\ldots, n_m} \omega_1^{n_1} \cdot \omega_2^{n_2} \cdots \omega_m^{n_m} \\ = \frac{N!}{\prod\limits_{i=1}^m n_i!} \prod\limits_{i=1}^m \omega_i^{n_i} \\ = N!\prod\limits_{i=1}^m \frac{\omega_i^{n_i}}{n_i!}$$

$\endgroup$
  • $\begingroup$ Graham, thank you for answering my question and writing this rigorous and well-structured reply. I was also thinking about the multinomial coefficient. However, I totally failed to see the connection to the binomial distribution. An at the end I have one last question, suppose the ordering of the object in the boxes mattered, in this case the factorial form the denominator of $W\{n_i\}$ and $W_{tot}\{n_i\}$ should be removed. Is this correct? $\endgroup$ – Alexander Cska May 20 '14 at 7:41
  • $\begingroup$ The reason order inside the boxes doesn't matter is because ultimately you are only concerned with the number of items in the boxes, not their identity. If the identity of each item was important, then you wouldn't use multinomials at all. There would be just $1$ way to arrange each unique sequence; and the probability of that specific arrangement would be: $\prod\limits_{i=1}^{m} \omega_i^{n_i}$ $\endgroup$ – Graham Kemp May 20 '14 at 8:13

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.