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.

  • 1
    Do you want the chosen subsets to be _disjoint_ so that they form a _partition_ of the elements into $X$ groups of $Y$? This seems to be what you mean, but you do not say so explicitly.2012-11-07
  • 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
    Great. For reference, does this problem have an "official" name?2012-11-07
  • 0
    @Massimo: I don’t know of one.2012-11-07