2
$\begingroup$

Given the integers $[1, ck]$, they will be partitioned into $c$ subsets of size $k$. I want to count the number of unique versions of each subset (where order matters).

Clearly, there are ${ck \choose k}$ different assignments of integers to a given subset, and for a given assignment, there are $k!$ different orders for that assignment. However, I want to know the total number of unique versions of all subsets, I'm concerned that following the above reasoning for each subset independently, I may end up over counting.

It seems like there should be a simple combinatorial argument for what I want to count, so I suspect that this could be already answered in some other question, but I couldn't find it.

$\endgroup$

1 Answer 1

2
$\begingroup$

You are correct that taking one ordered subset of size $k$ from a set of $ck$ can be done in ${ck \choose k}k!=\frac {(ck)!}{(ck-k)!}$ ways. Having done that, you can pick the second subset in ${ck-k \choose k}k!=\frac {(ck-k)!}{(ck-2k)!}$. If you keep going, the product will be exactly $(ck)!$. But you have overcounted. Each set of subsets can be listed in $c!$ different orders, so the final answer is $\frac {(ck)!}{c!}$

A combinatorial view is that one way to do this is just order the $ck$ elements. The first subset is the first $k$ items, the second the next $k$ and so on. Then recognize the permutations of the subsets to get the $c!$ divisor.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .