1
$\begingroup$

The question I'm looking at is:

Andy, Bill, Carl and Dave are 4 students on a team of 10. 5 must be chosen for a tournament, how many teams can be picked if Andy or Bill or Carl or Dave must be on the team.

Using the inclusion-exclusion principle:

Let $A_1 =$ teams with Andy, $A_2 =$ teams with Bill, ect.

$$|A_i| = {9 \choose 4}= 126$$

$$|A_i \cap A_j| = {8 \choose 3} = 56\text{ for }i \neq j$$

$$|A_i \cap A_j \cap A_k| = {7 \choose 2} =21\text{ for }i \neq j \neq k$$

$$|A_1 \cap A_2 \cap A_3 \cap A_4| = {6 \choose 1} = 6$$

So then $|A_1 \cup A_2 \cup A_3 \cup A_4| = 4(126) - 6(56) + 3(21) - 6 = 225$

But when I use the complements principle to subtract all teams without Andy, Bill, Carl, and Dave from all teams I get:

$${10 \choose 5} - \displaystyle{6 \choose 5} = 252 - 6 = 246$$

which is not the same. So I'm clearly doing something wrong with one of these but I don't know which one is wrong.

$\endgroup$
  • $\begingroup$ Why did you add $3(21)$? $\endgroup$ – Will Orrick Apr 1 '13 at 1:25
  • $\begingroup$ Because the 3 sets $A_1 \cap A_2 \cap A_3, A_1 \cap A_2 \cap A_4, A_2 \cap A_3 \cap A_4$ all have 21 different teams and I'm using the inclusion exclusion principle to determine $|A_1 \cup A_2 \cup A_3 \cup A_4|$ $\endgroup$ – MangoPirate Apr 1 '13 at 1:30
  • $\begingroup$ @MangoPirate : I improved both your TeX formatting and your spelling. Note that "compliment" with an "i" and "complement" with an "e" are two different words that mean two different things. The complement (with an "e") of $A$ is something that together with $A$ makes a complete whole. The resemblance to the spelling of "complete" is not coincidental and enables you to remember which is which. $\endgroup$ – Michael Hardy Apr 1 '13 at 1:30
  • 1
    $\begingroup$ @MangoPirate : The coefficients of the other three terms, namely 4, 6, and 1, are all numbers of the form $\binom{4}{j}.$ The number 3 is the only one that doesn't fit this pattern. Could that be a sign that something's wrong? $\endgroup$ – Will Orrick Apr 1 '13 at 1:33
  • 1
    $\begingroup$ You forgot about $A_1\cap A_3\cap A_4$. $\endgroup$ – André Nicolas Apr 1 '13 at 1:33
0
$\begingroup$

Community wiki answer so the question can be marked as answered:

As noted in the comments, the $21$ for $|A_i \cap A_j \cap A_k|$ should be multiplied by $4$, not by $3$, since there are $4$ ways to omit one of $4$ students and leave $3$.

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