A set of $n$ distinct items divided into $r$ distinct groups

Question

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)

Answer 1

You can permute all the $n$ distinct objects in a line. To make $r$ groups of these, take the first $n_1$ elements in this permutation and put them in group 1, the next $n_2$ elements and put them in group 2, etc. So, each permutation of $n$ elements is division of those elements in $r$ such groups. However, this division isn't unique, since the number of permutations of $n$ elements also includes permutations within the group's elements, even if they have the same elements. You divide $n!$ with the number of permutations of the first group, then second, and so on.

Another way of looking at it is first choose $n_1$ items from $n$, assign them to group 1, then choose $n_2$ items from $n-n_1$, assign those to group 2, and so on.

Answer 2

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