Number of ways of forming 10 student committee from 5 classes of 30 students each

Question

There are 5 classes with 30 students each. How many ways can a committee of 10 students be formed if each class has to have at least one student on the committee?

I figured that we first have to choose 5 people from each class, so there are $10^5$ options. There remain total of 29*5=145 students to choose from, and we can fill remaining 5 spots any way we want, i.e., $\binom{145}{5}$ options. Thus, I thought answer would be $$10^5 \dot\ \binom{145}{5} $$.

Apparently this is the wrong answer. I can see how the inclusion/exclusion principle also leads to the right answer. That is, $$ {150 \choose 10}- 5{120 \choose 10} + {5 \choose 2}{90 \choose 10} - {5 \choose 3}{60 \choose 10} + {5 \choose 4}{30 \choose 10} $$

I don't see though what I overlooked and why my answer is different?

Any advice on when to simply use inclusion/exclusion and when to use other methods?

Answer 1

You are over counting.

Suppose, for a simpler example, you had two classes of three students $\{a,b,c\},\{d,e,f\}$ and have count ways to form distinct committees of three that includes at least one student from each class.

Your method would have you count ways to pick one from $\{a,b,c\}$, one from $\{d,e,f\}$, and one from the remainder. $\binom 31\binom 31\binom 41$ ways; $36$.   So you could pick $a$ and $d$ then $b$ and form committee $\{a,b,d\}$.   Another ways is to pick $b$ and $d$, then $a$, to form.... the same committee, $\{a,b,d\}$.

---

So rather, we count the total ways to select three from six and use PIE.   That is $\binom 63-2\binom 33+\binom 03$, or $18$.

Which should equal ways to select two from $\{a,b,c\}$ and one from $\{d,e,f\}$ and ways to select one from $\{a,b,c\}$ and two from $\{d,e,f\}$.   $\binom 32\binom 31\times 2$.   Which is indeed $18$.

Answer 2

Here is how it works without inclusion-exclusion.

There are 7 ways of partitioning 10 into 5 positive parts. The number may be checked here https://oeis.org/A008284

The problem is similar to a poker game hands problem but here we have 5 colors and 30 values.

For each kind of "hand" we have to do the specific calculus.

$case \ 10=6+1+1+1+1$ :

there are $\binom{5}{1}$ choices of the long color. For each one, there are $\binom{30}{6}$ choices of the values. For each other short color there are ${\binom{30}{1}}$ choices, for a total of :

$\binom{5}{1} \binom{30}{6}{\binom{30}{1}}^4$

$case \ 10=5+2+1+1+1$ :

there are $\binom{5}{1}$ choices of the long color. There are $\binom{4}{1}$ choices for the color of a pair. For the long color, there are $\binom{30}{5}$ choices of the values. For the pair there are ${\binom{30}{2}}$ choices; the total is for a total of:

$\binom{5}{1} \binom{4}{1} \binom{30}{5} \binom{30}{2} {\binom{30}{1}}^3$

Let's write for the sake of comparing the complete formula:

$$\binom{5}{1} \binom{30}{6}{\binom{30}{1}}^4 + \binom{5}{1} \binom{4}{1} \binom{30}{5} \binom{30}{2} {\binom{30}{1}}^3 + \binom {5}{1} \binom{4}{1}\binom{30}{4}\binom{ 30}{3}\binom{30}{1}^3+ \binom{5}{1} \binom{4}{2} \binom{ 30}{4} \binom{ 30}{2}^2 \binom{30}{1}^2 + \binom{5}{1} \binom{4}{2} \binom{ 30}{2} \binom{ 30}{3}^2 \binom{30}{1}^2 + \binom{5}{1} \binom{4}{1} \binom{ 30}{3} \binom{ 30}{1} \binom{30}{2}^3 + \binom{30}{2}^5 $$

After computing all seven cases, we get the required 645666069796875. I think, given the similarity with poker where there are involved a lot of money, someone would have invented in the last centuries a shorter way of computing hands.

The inclusion-exclusion is possible since we can manipulate that "at least one" and the calculus is shorter since the classes are equal.

Answer 3

and here is via weighted species and e.g.f.

Let $X, Y, Z, U, V$ be five sorts of students

Then $ A = X \cdot E_{29}(X) + E_2(X) \cdot E_{28}(X) + E_3(X) \cdot E_{27}(X) + E_4(X) \cdot E_{26}(X) + E_5(X) \cdot E_{25}(X) + E_6(X) \cdot E_{24}(X) $

reprezents possible choices for the representants of the first class of X-students.

Passing to e.g.f. and adding a counter $t$ for the number of cosen students from one class, one gets:

$ a = t { x \over 1!} {x^{29} \over 29!} + t^2 { x^2 \over 2!} {x^{28} \over 28!} + \dots + t^6 { x^6 \over 6!} {x^{24} \over 24!} = ( { 30! \over 1! 29!}t + { 30! \over 2! 28!}t^2 + \dots + { 30!\over 6! 24!})t^6 \frac {x^{30}} {30!} $

Similarly we get

$ b = ( { 30! \over 1! 29!}t + { 30! \over 2! 28!}t^2 + \dots + { 30!\over 6! 24!})t^6 \frac {y^{30}} {30!}$

and so on.

By multiplying the obtained $a(t,x).b(t,y). \cdots .e(t,v)$ and then taking the coefficient of

$t^{10} \frac {x^{30}} {30!} \cdots \frac {v^{30}} {30!} $

one gets $645666069796875$.