4
$\begingroup$

I suppose that this question has already been asked, but I couldn't find it. Suppose we have a set $A$ with $nk$ elements. How many partitions of this set into sets of k elements are there?. For $n=k=2$, there are 3:

$\{\{\{1,2\}, \{3,4\}\}, \{\{1,3\}, \{2,4\}\}, \{\{1,4\},\{2,3\}\}$

NOTE: The case $n=2$ is solved here: Counting the number of partitions having blocks of cardinality 2 and non-distinct elements

$\endgroup$
4
$\begingroup$

One way to solve it: first put all $nk$ items in order: there are $(nk)!$ ways. Now chop them into blocks of $k$ and you have a partition. Each block can be reordered in $k!$ ways, then the blocks can be put in order in $n!$ ways. In all, we have $\frac{(nk)!}{(k!)^nn!}$ ways to make the partition.

Another way is to say there are ${nk \choose k}$ ways to get the first partition, ${(n-1)k \choose k}$ to get the second, and so on. Again you can choose the partitions in $n!$ orders. This gets you the same answer.

$\endgroup$

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.