PIE: proof by counting

Recall the setup: we have a universal set $U$ and a collection of subsets $A_1$ , $A_2$ , $A_3$ , and so on, up to $A_n$ . PIE claims that we can compute the number of elements of $U$ that are in none of the $A_i$ (that is, $|U| - |A_1 \cup A_2 \cup \dots \cup A_n|$ ) if we take the sizes of every possible intersection of some of the sets (including none of them, which yields $U$ itself), and alternately add (if we intersected an even number of sets) or subtract (if odd). That is, using formal notation,

$\displaystyle \left| |U| - \bigcup_{i = 1}^n A_i \right| = \sum_{S \subseteq \{1, \dots, n\}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|$

Last time, we proved this using some algebra. This time, we’re going to prove it by counting. Consider a particular (arbitrary) element $x \in U$ . We want to see how many times $x$ gets counted: we count $1$ for each intersection containing $x$ that gets added, and $-1$ for each intersection containing $x$ that gets subtracted. In the end, $x$ should end up being counted exactly once if it’s not in any of the $A_i$ , and exactly zero times otherwise.

So, suppose $x$ is in exactly $k$ of the sets $A_i$ . Let’s consider intersections of different numbers of sets and see how many times $x$ gets counted in each.

There is only one way to intersect $0$ of the sets, which gives $U$ itself. $x$ is definitely in there, so including $|U|$ means $x$ gets counted once.
“Intersecting one set” sounds nonsensical, but really it just means we are considering the sets $A_1$ , $A_2$ , etc. by themselves; these all get subtracted. By assumption, $x$ is in exactly $k$ of them, so it gets counted $-k$ times.
There are a bunch of different ways to intersect two sets, $A_i \cap A_j$ . How many of them contain $x$ ? Of course $x$ is in $A_i \cap A_j$ exactly when it is in both $A_i$ and $A_j$ , so the number of two-set intersections containing $x$ is the number of different ways to pick two out of the $k$ sets containing $x$ , that is, $\binom{k}{2}$ . These all get added, so $x$ is counted $\binom{k}{2}$ times.
Likewise with intersections of three sets: the only way for $x$ to end up in an intersection of three sets is if $x$ is contained in all of them, and there are $\binom{k}{3}$ ways to choose three out of the $k$ sets containing $x$ . These get subtracted.

In general, there are $\binom{k}{i}$ different intersections of exactly $i$ sets which contain $x$ , up through $i = k$ . So, all in all, $x$ gets counted a grand total of

$\displaystyle\binom{k}{0} - \binom{k}{1} + \binom{k}{2} - \binom{k}{3} + \dots \pm \binom{k}{k}$

times. Now, when $k = 0$ , this is just $\binom{0}{0} = 1$ , which makes sense: if $x$ is in none of the $A_i$ , then it gets counted exactly once (as a part of $U$ 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 $x$ is in at least one of the $A_i$ then we ultimately want it to be counted zero times.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →