Let A be a 100-element set. Count the number of partitions of A into 20 parts of size 5.

Question

First, I've defined a relation $R$ on $A$ such that $aRb$ if $a$ and $b$ are in the same part of a partition where $a,b\in A$.

I know I need to count the number of equivalence classes produced form this relation. But I'm not sure how to proceed.

Answer 1

Sketch:

• The number of $5$-element sets is $\binom{100}{5}$ since we're choosing $5$ elements from $100$.

• The number of pairs of $5$-element sets is $\frac{1}{2}\binom{100}{5}\binom{95}{5}$ since we're choosing $5$ elements twice, but we must account for the fact that the same pair could occur in the opposite order.

• If we continue in this way, the number of $5$-element sets is $$ \frac{1}{20!}\binom{100}{5}\binom{95}{5}\binom{90}{5}\binom{85}{5}\binom{80}{5}\binom{75}{5}\binom{70}{5}\binom{65}{5}\binom{60}{5}\binom{55}{5}\binom{50}{5}\binom{45}{5}\binom{40}{5}\binom{35}{5}\binom{30}{5}\binom{25}{5}\binom{20}{5}\binom{15}{5}\binom{10}{5}\binom{5}{5} $$ This can be expressed better using multinomial coefficients, but if you work out all the cancellations, you'll get $$ \frac{100!}{20!(5!)^{20}}. $$

Answer 2

Here is one way to think about this conceptually/visually:

Randomly line up all $100$ objects. This can be done in $100!$ ways.

From this we create groups of $5$ in order, i.e. objects 1 through 5 are a group, objects 6 through 10 a second, etc.

But now we realize that the order of the 5 in each group does not matter to the nature of the group. So, we need to divide the $100!$ by $5!$ for each of the $20$ groups (since there are $5!$ ways to order the 5 in each group, and each such ordering was counted as a different ordering in the original $100!$) so we get:

$$\frac{100!}{(5!)^{20}}$$

Finally, the order of the $20$ groups does not matter either, so divide by $20!$ to get our final answer:

$$\frac{100!}{20!(5!)^{20}}$$