A combinatorial proof: PIE a la mode!

Continuing from my last post in this series, we’re trying to show that S = n!, where S is defined as

\displaystyle S = \sum_{i=0}^n (-1)^i \binom{n}{i} (k+(n-i))^n

which is what we get when we start with a sequence of n+1 consecutive nth powers and repeatedly take successive differences.

Recall that we defined M_a as the set of all functions from a set of size n (visualized as n blue dots) to a set of size k + n (visualized as k yellow dots on top of n blue dots) such that the blue dot numbered a is missing. I also explained in my previous post that the functions with at least one blue dot missing from the output are exactly the “bad” functions, that is, the functions which do not correspond to a one-to-one matching between the blue dots on the left and the blue dots on the right.

As an example, the function pictured above is an element of M_1, as well as an element of M_3. (That means it’s also an element of the intersection M_1 \cap M_3—this will be important later!)

Let F be the set of all functions from n to k+n, and let P be the set of “good” functions, that is, the subset of F consisting of matchings (aka Permutations—I couldn’t use M for Matchings because M is already taken!) between the blue sets. We already know that the number of matchings between two sets of size n, that is, |P|, is equal to n!. However, let’s see if we can count them a different way.

Every function is either “good” or “bad”, so we can describe the set of good functions as what’s left over when we remove all the bad ones:

\displaystyle P = F - \bigcup_{a=1}^n M_a

(Notice how we can’t just write P = F - M_1 - M_2 - \dots - M_n, because the M_a sets overlap! But if we union all of them we’ll get each “bad” function once.)

In other words, we want to count the functions that aren’t in any of the M_a. But this is exactly what the Principle of Inclusion-Exclusion (PIE) is for! PIE tells us that the size of this set is

\displaystyle |P| = |F| - \left|\bigcup_{a=1}^n M_a \right| = \sum_{T \subseteq \{1 \dots n\}} (-1)^{|T|}\left| \bigcap_{a \in T} M_a \right|,

that is, we take all possible intersections of some of the M_a, and either add or subtract the size of each intersection depending on whether the number of sets being intersected is even or odd.

We’re getting close! To simplify this more we’ll need to figure out what those intersections \bigcap_{a \in T} M_a look like.


What does M_a \cap M_b look like? The members of M_a \cap M_b are exactly those functions which are in both M_a and M_b, so M_a \cap M_b contains all the functions that are missing both a and b (and possibly other elements). Likewise, M_a \cap M_b \cap M_c contains all the functions that are missing (at least) a, b, and c; and so on.

Last time we argued that |M_a| = (k + (n-1))^n, since functions from n to k+n that are missing a can be put into a 1-1 matching with arbitrary functions from n to k + (n-1), just by deleting or inserting element a:

So what about an intersection—how big is M_a \cap M_b (assuming a \neq b)? By a similar argument, it must be (k + (n-2))^n, since we can match up each function in M_a \cap M_b with a function from n to k+(n-2): just delete or insert both elements a and b, like this:

Generalizing, if we have a subset T \subseteq \{1, \dots, n\} and intersect all the M_a for a \in T, we get the set of functions whose output is missing all the elements of T, and we can match them up with functions from n to k + (n-|T|). In formal notation,

\displaystyle \left| \bigcap_{a \in T} M_a \right| = (k + (n-|T|))^n

Substituting this into the previous expression for the number of blue matchings |P|, we get

\displaystyle |P| = \sum_{T \subseteq \{1 \dots n\}} (-1)^{|T|}(k + (n-|T|))^n

Counting subsets

Notice that the value of (-1)^{|T|}(k + (n-|T|))^n depends only on the size of the subset T and not on its specific elements. This makes sense: the number of functions missing some particular number of elements is the same no matter which specific elements we pick to be missing.

So for each particular size |T| = i, we are adding up a bunch of copies of the same value (-1)^i (k + (n-i))^n—as many copies as there are different subsets of size i. The number of subsets T of size i is \binom n i, the number of ways of choosing exactly i things out of n. Therefore, if we add things up size by size instead of subset by subset, we get

\begin{array}{rcl} |P| &=& \displaystyle \sum_{\text{all possible sizes } i} (\text{number of subsets of size } i) \cdot \left[(-1)^{i}(k + (n-i))^n \right] \\[1em] &=& \displaystyle \sum_{i=0}^n \binom n i (-1)^{i}(k + (n-i))^n\end{array}

But this is exactly the expression for S that we came up with earlier! And since we already know |P| = n! this means that S = n! too.

And that’s essentially it for the proof! I think there’s still more to say about the big picture, though. In a future post I’ll wrap things up and offer some reflections on why I find this interesting and where else it might lead.

About Brent

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