There are 100 people in total. In how many ways can we form 15 committees of 20 people each such that each person is on 3 committees?
I guess the number of ways to form a committee of 20 people from 100 is ${100 \choose 20}$, is that correct? Now how to incorporate the condition that each person is on 3 committees?
Any hint is appreciated. Thanks!
Best Answer
Interesting lecture. Finding the number of committees is a little contrary to his point, but here's an upper bound at least.
Since each person is on 3 committees, pretend there are 3 of each person, say 42, 42', and 42''. Each person and their clones make up 300 potential committee members. The number of ways to allocate them into 15 committees of 20 is $$ {300 \choose 20}{280 \choose 20}\cdots{40 \choose 20}{20 \choose 20} = {300 \choose 20, \ldots, 20} $$ (using a multinomial coefficient) which is around $4.94 \times 10^{338}$. This creates 15 committees of 20 and, e.g., 42, 42', and 42'' are each included. The over-counting arises because this lets clones be on the same committee: There are even committees where "three" of the members are 42, 42', and 42''. So committees with such repetition need to be removed. However that works out, the final answer will still be huge.