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

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)

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

• Thank you for your help, really appreciate it
– Hiro
Jul 26 '20 at 8:27

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.

• Thank you for your help, I'm really appreciate it.
– Hiro
Jul 26 '20 at 8:27