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 $n$ th 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.

Intersections

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.