# How many ways there are of choosing X subsets of Y elements out of a set?

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.

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

## 1 Answer

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

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