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
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.
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!}$$