5
$\begingroup$

I'm a bit confused as to when you should use the Incl/Excl principle. Take for example the following problem:

How many 13-card hands can be selected from the standard 52-card deck with exactly four spades or exactly four diamonds?

My university tutor solved this problem by using the principle. My theory would be that you need to use it in this case because a 13-card hand with exactly four spades can also contain four diamonds, and a hand with exactly four diamond can also contain four spades - so you end up counting too many times.

Is there a trick or a general rule for when you should use it?

Sub-question: My tutor wrote this for choosing exactly four spades, and I believe there might be a mistake:

$c(13,4) * c(9,39)$

$c(13,4)$ is the number of ways to choose four positions for the spades
$c(9,39)$ is the number of ways to choose the remaining 9 cards that are not spades

But isn't it missing another $c(13,4)$ to choose the four spades out of 13 spades?

  • 1
    If you want an example where Inclusion-Exclusion can be used but may not be the easiest approach, see http://math.stackexchange.com/questions/23685/number-of-ways-to-get-exactly-one-3-of-a-kind-from-9-dice2011-05-22

2 Answers 2

2

First and foremost, your notation $c(9,39)$ should read $c(39,9)$. That is presumably a typo. Now:

The inclusion-exclusion principle helps you find the cardinality of the sets $A \cup B$, $A \cup B \cup C$, $A \cup B \cup C \cup D$, etc. In your case, you have to find the cardinality of the set $A \cup B$, where $A$ is the event that you draw exactly four spades and $B$ is the event that you draw exactly four diamonds. If $|A|$ denotes the cardinality (or number of elements) in the set $A$, then

$ |A \cup B| = |A| + |B| - |A \cap B|. $

This makes intuitive sense, since if you want to count the number of elements in the set $A \cup B$, you count the number of elements in $A$, you count the number of elements in $B$ and you subtract the number of elements in $A \cap B$, since they were counted twice.

To find $|A|$ or the number of $13$ card hands which have exactly four spades, you need to choose $4$ spades from the possible $13$ and $9$ non spades from the rest of the deck. The number of ways of doing this is

$ c(13,4) \cdot c(39,9) = 151519319380. $

  • 1
    @Arvin. Right on.2011-05-22
2

Don't really like to give general rules or tricks, since then looking for them can interfere with the analysis of a problem. But the presence of or means we are trying to count the union of two sets $A$ and $B$. And sometimes the best way to count a union is to count $A$, count $B$, count what they have in common, and do the obvious thing. Your jntuitive explanation of the "why" in this case was clear and correct.

Your tutor's answer is right, but your description of it is not. We are counting the number of hands, order is irrelevant. The $c(13,4)$ in the answer comes not from the location of the spades. It actually counts the number of ways of choosing $4$ spades from the $13$. For every way of choosing the spades, there are $c(39,9)$ ways to choose the remaining cards (you kind of typed it backwards), so the number of $4$-spade hands is $C(13,4)C(39,9)$

  • 0
    Thanks for that. Of course the order doesn't matter since it's a card hand - what was I thinking? :)2011-05-22