Recall the setup: we have a universal set and a collection of subsets , , , and so on, up to . PIE claims that we can compute the number of elements of that are in none of the (that is, ) if we take the sizes of every possible intersection of some of the sets (including none of them, which yields itself), and alternately add (if we intersected an even number of sets) or subtract (if odd). That is, using formal notation,
Last time, we proved this using some algebra. This time, we’re going to prove it by counting. Consider a particular (arbitrary) element . We want to see how many times gets counted: we count for each intersection containing that gets added, and for each intersection containing that gets subtracted. In the end, should end up being counted exactly once if it’s not in any of the , and exactly zero times otherwise.
So, suppose is in exactly of the sets . Let’s consider intersections of different numbers of sets and see how many times gets counted in each.
There is only one way to intersect of the sets, which gives itself. is definitely in there, so including means gets counted once.
“Intersecting one set” sounds nonsensical, but really it just means we are considering the sets , , etc. by themselves; these all get subtracted. By assumption, is in exactly of them, so it gets counted times.
There are a bunch of different ways to intersect two sets, . How many of them contain ? Of course is in exactly when it is in both and , so the number of two-set intersections containing is the number of different ways to pick two out of the sets containing , that is, . These all get added, so is counted times.
Likewise with intersections of three sets: the only way for to end up in an intersection of three sets is if is contained in all of them, and there are ways to choose three out of the sets containing . These get subtracted.
In general, there are different intersections of exactly sets which contain , up through . So, all in all, gets counted a grand total of
times. Now, when , this is just , which makes sense: if is in none of the , then it gets counted exactly once (as a part of itself), just as it should be. Otherwise, we have an alternating sum of successive binomial coefficients—that is, we add up a row of Pascal’s triangle with alternating signs. Such an alternating sum of binomial coefficients is always zero, which I proved in another blog post. And that’s also as it should be: if is in at least one of the then we ultimately want it to be counted zero times.