2
$\begingroup$

Question:

There are $4$ classes in a school, each consisting of $15$ children. A committee consisting of $12$ children shall be chosen. In how many ways can this be done, if it is required that the committee must have at least $1$ child from each class?

I know that the correct way to solve this problem is by using the sieve principle. But my first attempt was the following and I can't figure out why it doesn't work:

$i)$ Pick one child from each class and put them in the committee ($15^4$ ways). This guarantees that there is one student from every class in the committee.

$ii)$ Pick the rest from the remaining 60-4 = 56 children ($\begin{pmatrix}56 \\8\end{pmatrix}$ ways)

So there should be $15^4\begin{pmatrix}56 \\8\end{pmatrix}$ ways to do this. That's the wrong answer afaik, can anyone point out the flaw?

$\endgroup$
  • 1
    $\begingroup$ You are double counting picking $2$ children from the same class. A child picked by $15^4$ is the same as a child picked by $56\choose8$. $\endgroup$ – Element118 Jan 2 '16 at 14:00
  • 1
    $\begingroup$ I suggest to make cases like $(1,1,9,1),(2,2,2,9)..$ and laatly mutiply by $4!$ $\endgroup$ – Archis Welankar Jan 2 '16 at 14:00
  • 1
    $\begingroup$ The possibility that e.g. Arnold is picked out as one of the $4$ in i) and gets company of Betty out of his class is counted more than once. Also Betty can be picked out in the first step to get company of Arnold in the second step. $\endgroup$ – drhab Jan 2 '16 at 14:01
  • $\begingroup$ You need to divide $15^4$ by $4!$, otherwise you say that $ABCD \neq DABC$ etc. $\endgroup$ – Wojciech Karwacki Jan 2 '16 at 14:03
1
$\begingroup$

Use the principle of inclusion and exclusion. Say a committee has property $i$ if it doesn't have members of class $i$. The number of ways to select the $12$ committee members We want the number of committees without properties.

The number of committees with $r$ properties is just selecting children among $4 - r$ classes, i.e., $\binom{4}{r} \binom{(4 - r) 15}{12}$. By the principle's formula, you are asked for:

$$\sum_{0 \le r \le 4} (-1)^{4 - r} \binom{4}{r} \binom{15 (4 - r)}{12} = 1284837715525$$

(Last number courtesy of my tame computer algebra system, maxima)

$\endgroup$

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.