Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.