1
$\begingroup$

Please forgive me if this looks like a trivial question; I'm quite sure this is a well known problem, but I don't know its formal name, so I've been so far unable to look it up on Google.

Given a set containing $X \cdot Y$ elements, how many ways there are of choosing $X$ disjoint (non-overlapping) subsets containing $Y$ elements each? Ordering of subsets is not relevant, thus each permutation of the same subsets should only appear once.

  • 0
    Good point, question edited.2012-11-07

1 Answers 1

1

First we’ll count ordered collections of $X$ $Y$-element subsets. There are $\binom{XY}Y$ ways to choose the first $Y$-element subset, $\binom{XY-Y}Y=\binom{(X-1)Y}Y$ ways to choose the second, $\binom{(X-2)Y}Y$ ways to choose the third, and so on, for a total of

$\prod_{k=1}^X\binom{kY}Y=\binom{XY}{\underbrace{Y,Y,\dots,Y}_X}=\frac{(XY)!}{Y!^X}$

ordered collections of $X$ $Y$-element subsets. This counts each unordered family $X!$ times, so the final figure is

$\frac1{X!}\prod_{k=1}^X\binom{kY}Y=\frac1{X!}\binom{XY}{\underbrace{Y,Y,\dots,Y}_X}=\frac{(XY)!}{X!Y!^X}\;.$

  • 0
    @Massimo: I don’t know of one.2012-11-07