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.

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.