0
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you for your help, really appreciate it $\endgroup$
    – Hiro
    Jul 26 '20 at 8:27
0
$\begingroup$

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.

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

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.