Multinomial Coefficients
I was getting a bit confused by examples (5b) and (5c) where they choose basketball teams. The ordering of groups confused me. But then I resolved this by realizing that the groupings
- 12345, 67890
- 67890, 12345
are considered different when designating teams A and B. But they are the same when splitting ten kids to play a game.
But now consider this: we start with 4 people and we want to group them into groups of 3 and 1. The count of ways to do this is $\frac{4!}{3!1!}=4$. There is no way to change the order of the groupings since 3 is specified to be first and 1 is specified to be second. 4 is the count and there is no need or possible way of reducing the count for permutations of groups:
- 123,4
- 124,3
- 134,2
- 234,1
Now consider this: we start with 4 people and we want to group them into groups of 2 and 2. The count of ways to do this is $\frac{4!}{2!2!}=\frac{4!}4=3!=6$:
- 12,34
- 13,24
- 14,23
- 23,14
- 24,13
- 34,12
Notice that we have permutations of groupings. For instance, the first grouping 12,34 is a permutation of the last grouping 34,12. And
- 12,34 ~ 34,12
- 13,24 ~ 24,13
- 14,23 ~ 23,14
So the count of possible groups where order is irrelevant is $\frac6{2!}=3$. That is, to get the combinations-of-groupings count, we must divide the permutations-of-groupings count by the factorial of the number of groupings.
So if $n=2^m$ distinct items are to be grouped into $m$ groups of size $2$, then the count without permutations is
$$ \frac{n!}{2^{m}(m!)} $$
More generally, if $n=r^m$ distinct items are to be grouped into $m$ groups of size $r$, then the count without permutations is
$$ \frac{n!}{(r!)^{m}(m!)} $$
Now when you look at example (5d), it is pretty clear.