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$
6
  • $\begingroup$ Why did you add $3(21)$? $\endgroup$
    – Will Orrick
    Commented Apr 1, 2013 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
    Commented Apr 1, 2013 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
    Commented Apr 1, 2013 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
    Commented Apr 1, 2013 at 1:33
  • 1
    $\begingroup$ You forgot about $A_1\cap A_3\cap A_4$. $\endgroup$
    – André Nicolas
    Commented Apr 1, 2013 at 1:33

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .