A set of $n$ distinct items is to be divided into $r$ distinct groups of respective sizes $n_1, n_2, n_3$, where $\sum_{i=1}^{r}n_i=n$.
How many different division are possible ?
Because every permutation yields a division of the items and every possible division results from some permutation, it follows that the number of divisions of $n$ items into $r$ distinct groups of sizes $n_1, n_2, … , n_r$ is the same as the number of permutations of $n$ items of which $n_1$ are alike, and $n_2$ are alike, …, and $n_r$ are alike.
Can somebody explain why and how every permutation yields a division of the items and every possible division results from some permutation part?
(This question is taken from Sheldon.M.Ross First Course in Probability book)
Best Answer
Suppose our items are labeled $1,2,3,4$ and we want to divide them into two groups of size $2$. Every permutation corresponds to a division where the first two go to group 1 and the second two to group 2:
1 2 | 3 4
1 3 | 2 4
2 3 | 4 1
and so on.
There are $4$ permutations, however, fixing all the objects and permutating the leftmost two doesn't change a thing (12|34 and 21|34 represent the same sets) so you divide by $2!$ to account for the possible permutations of the leftmost two. The same with the rightmost two. In the general case, you get: $$\frac{n!}{n_1!\ldots n_r!}$$