Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.