Please refer to the following excerpt from "Pattern Recognition and Machine Learning" Bishop.

We can understand this alternative view of entropy by considering a set of N identical objects that are to be divided amongst a set of bins, such that there are $n_i$ objects in the $i^{th}$ bin. Consider the number of different ways of allocating the objects to the bins. There are N ways to choose the first object, $(N - 1)$ ways to choose the second object, and so on, leading to a total of N! ways to allocate all N objects to the bins, where N! (pronounced ‘factorial N ’) denotes the product N \times (N - 1) $\times \ldots \times 2 \times > 1$. However, we don’t wish to distinguish between rearrangements of objects within each bin. In the $i^{th}$ bin there are $n_{i}!$ ways of reordering the objects, and so the total number of ways of allocating the N objects to the bins is given by: $${\bf W} = \frac{N!}{\prod_{i}n_{i}!}$$ which is called multiplicity.

I am confused about the bold-faced part.

If bin 1 were to have n=1 object and bin 2 were to have 2 objects and so on, then the number of options for placing the objects in $i^{th}$ bin would be like - (with successive bin have only remaining objects to choose from):

$$^{N}C_{1} * ^{N-1}C_{2} * ^{N-3}C_{3}* ^{N-6}C_{4} \cdot \cdot $$

Were am I missing the point?

P.S.: If each bin has only one object, then I can understand N!.


You are not missing anything. You simply found another derivation of the same relationship.

We know that

$$^{n}C_{k} = \frac{n!}{k!(n-k)!} $$

If we expand the terms in your product,

$$^{N}C_{1} * ^{N-1}C_{2} * ^{N-3}C_{3}* ^{N-6}C_{4} \cdot \cdot $$

, we get

$$\frac{n!}{1!(n-1)!} \cdot \frac{(n-1)!}{2!(n-3)!} \cdot \frac{(n-3)!}{3!(n-6)!} \cdot \frac{(n-6)!}{4!(n-10)!} \dots $$

If we simplify the factorials,

$$\frac{n}{1!} \cdot \frac{(n-1)(n-2)}{2!} \cdot \frac{(n-3)(n-4)(n-5)}{3!} \cdot \frac{(n-6)(n-7)(n-8)(n-9)}{4!} \dots $$

And now it's obvious that this is

$$ \frac{n!}{\prod_i i!} $$

  • $\begingroup$ Got it! Thanks for clear, prompt response $\endgroup$ – Continue2Learn Jun 5 '19 at 9:49

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.