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?

  • 0
    Have you tried it also with looking at the Vann Diagram of the sets?2011-05-22
  • 0
    I'm not sure what the venn diagram would look like but would it be something like this? http://img851.imageshack.us/img851/9831/capturehj.jpg2011-05-22
  • 0
    Yes I suppose looking at the venn diagram I made there, it does make sense. I guess venn diagrams are one way to tell you need to use the principle.2011-05-22
  • 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. $$

  • 0
    Thanks DJC, that confirms what I thought as well. This explanation works for my particular problem, but I was looking for a general rule/trick to figure out when best to use the principle and when not to use it. I suppose it's different for every problem so there aren't any rules or tricks2011-05-22
  • 0
    Hmm, how would you find the cardinality of A intersect B?2011-05-22
  • 0
    Well, what _is_ $A \cap B$ here?2011-05-22
  • 0
    It would be the set of all card hands which contain Exactly 4 Spades AND 4 Diamonds. I suppose then it would be c(13,4) * c(13,4) * c(26, 5) ?2011-05-22
  • 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