In a previous post we derived the following expression:

We are trying to show that , in order to show that starting with a sequence of consecutive th powers and repeatedly taking successive differences will always result in . Last time we also made a picture of a typical function from a set of size to a set of size , which looks like this:

Here’s the plan of action from this point:

• Start with all the functions from a set of size to a set of size (i.e. all possible pictures like the above).
• Subtract off the “bad” functions which don’t correspond to matchings between the blue dots.
• We will be left with only matchings, of which we know there are .
• Find that the right expression to count the functions via this procedure is exactly .
• Rejoice!

Bad functions

What makes a function “bad”? Based on the discussion in my previous post, it seems that there are two things that can make a function “bad”, that is, prevent it from being a matching between the blue sets:

• An arrow can point to one of the orange dots. This means there won’t be enough arrows left to cover all of the blue dots.
• Two arrows can “collide”, that is, point to the same blue dot on the right-hand side (if two arrows point to the same orange dot then it’s already bad because of the first reason). This means it can’t be a valid matching, because a matching has to match each blue dot on the left with exactly one blue dot on the right and vice versa.

The example function above has both these problems:

From another point of view, however, there is really only one thing that makes a function bad, which encompasses both points above: a function is bad if and only if there is at least one “missing” blue dot, that is, a blue dot on the right-hand side which is not pointed to by an arrow. On the one hand, if there is a missing blue dot, then the function obviously can’t be a matching, since the missing blue dot is unmatched. On the other hand, if there are no missing dots, then each dot must be matched with a unique dot on the left-hand side, since there are the same number of blue dots on both sides. (In fact, if a blue dot is missing, it will always be caused by one of the two problems listed above—there will either be an arrow pointing to an orange dot, or two arrows that collide.) Here is the same function again, but with the missing elements marked as “bad” by fading them out a bit:

Our goal is now to “subtract off” these bad functions, that is, the functions with at least one missing blue dot.

Counting bad functions

Let’s number the blue dots from to (with at the top), and define as the set of all functions from to where blue dot is missing ( is for “Missing”).

So, for example, the function from before is an element of , since element is missing:

How big is ? Well, if we just leave out the missing blue dot (and renumber the blue dots with numbers greater than ), we are left with a function from to ; conversely, every function from to can be made into a function from to with blue dot missing, just by inserting a new dot numbered (and again renumbering the dots with numbers ).

So, since we can put the function in in one-to-one correspondence with all the functions from a set of size to a set of size , the size of is just the number of such functions, that is, .

At this point, however, we run into a snag: as you can see, the example function we’ve been using is also an element of , since is missing too. And this is why we can’t simply subtract each of the and call it a day: the sets overlap, so if we subtract all of them we would be subtracting functions multiple times.

Hmm, subsets that overlap, and we want to count the things that are in none of the subsets… this is starting to sound familiar! We need some PIE, of course. In my next post we’ll start putting some of the pieces together!