## 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

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in combinatorics, pattern, proof and tagged , , , , . Bookmark the permalink.

### 1 Response to PIE: proof by counting

Comments are closed.