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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Nov 7 '12 at 12:48
  • $\begingroup$ Good point, question edited. $\endgroup$ – Massimo Nov 7 '12 at 13:06
1
$\begingroup$

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}\;.$$

$\endgroup$
  • $\begingroup$ Great. For reference, does this problem have an "official" name? $\endgroup$ – Massimo Nov 7 '12 at 13:07
  • $\begingroup$ @Massimo: I don’t know of one. $\endgroup$ – Brian M. Scott Nov 7 '12 at 15:43

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.