I’m supervising first-year undergraduates for Probability this term, and found myself discussing the Inclusion-Exclusion Principle with some of them earlier. It’s a very nice idea.
I grew up in a house with three cats. At meal times, each had his or her own bowl. But being cats, they never wanted to eat from their own bowls: the bowl next door always looked nicer (despite the food having come from the same tin). In how many ways could they all eat from the wrong bowl?
(With apologies to the cats, who were all very beautiful tabbies, and not those colours at all. My skills at drawing pictures on my computer are limited!)
Here they are with their rightful bowls. In how many ways can we mix them up so that no cat gets the right bowl? Well, grey cat had better not have the blue bowl, so it can have the green bowl or the yellow bowl. Let’s think about the former of those first. If grey cat has the green bowl, then we’d better make sure that ginger cat has the blue bowl (because it isn’t allowed the yellow one). And then white cat must have the yellow bowl. So once we’ve decided that grey cat has the green bowl, there’s only one possibility: this one.
What if grey cat takes a fancy to the yellow bowl? Then white cat must get the blue bowl (because it’s not allowed the green bowl), and ginger cat must get the blue bowl. So again just one possibility, namely this one.
So just two ways for each cat to get the wrong bowl, and it was pretty easy to work that out (and be sure that we’d found them all).
What would have happened if there had been more cats in the house (apart from an increase in the mayhem at mealtimes)? For example, if there had been 10 cats, in how many ways could they all have got the wrong bowls?
I think we need a new strategy. It’s going to be much harder to list them this time (try it, if you don’t believe me!). So let’s try to find another way to understand the problem with 3 cats, and hopefully it’ll be more amenable to generalisation.
A new strategy
We’ve got a whole bunch of ways of matching bowls to cats. In some of those ways, grey cat gets its own bowl (the blue one), and in some it doesn’t. Also, in some ways white cat gets its own bowl, and in some it doesn’t. And finally in some ways ginger cat gets its own bowl, and in some it doesn’t. We want to count the ways in which grey cat doesn’t get its bowl, and white cat doesn’t get its bowl, and ginger cat doesn’t get its bowl. We can represent this in a Venn diagram.
This rectangle is supposed to represent all the ways in which we can match bowls to cats. The set labelled G (for grey) contains those ways in which the grey cat gets the right bowl, and similarly for the other colours. The yellow and black areas together are supposed to represent the intersection of (for orange) and , for example, so between them they contain the ways in which both the ginger and the white cats get their correct bowls. So we want to count the ways in the outside blue region.
How can we do that? Let’s warm up with a slightly easier problem: just two sets. Here’s the picture.
Let’s try to find the size of the yellow region. I’ll write for the whole rectangle. So the size of the yellow region is the size of , written , minus the size of the bit covered by and . Let’s concentrate on that last bit, called the union of and , written .
We could think about , the size of plus the size of . Is that what we want? Not quite, because we’ve counted the purple region (the intersection of and , written ) twice. So we actually want .
Then we can find the size of the yellow region: it’s the size of the whole rectangle minus the size of the region covered by and . That is, the size of the yellow region is .
Let’s do a similar thing with three sets, and then we’ll go back to the problem with the cats and check our answer. Again, I’ll write for the whole rectangle. This time, we want to take the size of and remove the size of , the region covered by the three sets in the middle.
What’s the size of that union? Again, our first guess might be . But again that’s not quite right. We’ve counted the overlaps twice, so we should subtract them, to get . Is that right? Not quite, because we’ve subtracted the central black region (the intersection of all three sets) one too many times. So the size of the union is actually .
So the size of the yellow region is .
Let’s check this. What’s the size of in our cat problem? It’s the number of ways of matching bowls to cats. But that’s quite easy to work out. There are 3 ways to choose the bowl for grey cat, then 2 for white cat, then 1 for orange cat. So . So far so good.
What’s ? It’s the set of ways in which grey cat gets the right bowl. How many of those are there? Well, we’ve fixed it so that grey cat gets the right bowl, so then there are just 2 possibilities for white cat, and 1 for ginger cat, so . In just the same way, , and .
What about the intersection of and ? It’s the set of ways in which grey and white cats both get the right bowl. But then ginger cat must get the right bowl too, so there’s only one way for that. That is, . In the same way, and .
Finally, the intersection of all three sets is the set containing the one way in which each of the three cats gets the right bowl. So .
Now, let’s compute the expression we hope will give the answer, namely . That gives — which is the answer we were hoping for!
Of course, this is no proof, but it is reassuring (and hopefully helps illustrate the idea).
It turns out that one can prove an analogous result for any number of sets, and it is this that is usually called the Inclusion-Exclusion Principle. I think I’ll state it here for 3 sets, but I hope it’s reasonably clear how it extends to sets. You can see a statement of the general result on the Wikipedia page, for example.
Theorem (the inclusion-exclusion principle) Let , and be subsets of a finite set . Then .
How could one go about proving this (and, indeed, the corresponding result for sets)? One strategy is to use induction, using the result for sets to deduce the result for sets. But my favourite approach is to use indicator functions. I like it because it seems very clean, and seems to capture our idea about why the result ought to be true. But before I can tell you the argument, I’d better tell you what an indicator function is. Through all of the rest of the post, I’m going to work with the sets , , and in the statement of the principle above.
The indicator function of , written , records which elements of are in and which are not. Precisely, for an element of , we say that if is in , and if is not in .
How can we extract the size of if we know its indicator function? Well, we add up for all in . That is, . Why? Well, we count 1 in the sum each time is in , and 0 each time it isn’t — so we count each element of exactly once, which must give .
It turns out to be quite easy to write down the indicator functions of and in terms of the indicator functions of and .
The indicator function of is (just the product). Why? Well, if and only if is in , which happens if and only if is in both and , which happens if and only if and , which happens if and only if .
The indicator function of is . I’ll let you convince yourself of that — it’s a good exercise (and not too hard).
Now we can find the indicator function of . We have
Now that we know its indicator function, we can find the size of . We simply sum for all in . We get
and that’s just what we wanted!
The same idea works in general (for sets), it just takes a bit more care to write it out.
As I mentioned above, there’s a Wikipedia page about the inclusion-exclusion principle. I am not sure who first came up with the principle, so I’ll refer you to the Wikipedia page and you can read its assertions for yourself. The problem of matching bowls to cats in such a way that no cat gets the right bowl is an example of derangements (although that isn’t the standard example!). No rude remarks about deranged cats or their owners, please…