A combinatorial proof: counting bad functions

In a previous post we derived the following expression:

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

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

Here’s the plan of action from this point:

  • Start with all the functions from a set of size n to a set of size k+n (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 n!.
  • Find that the right expression to count the functions via this procedure is exactly S.
  • 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 1 to n (with 1 at the top), and define M_i as the set of all functions from n to k+n where blue dot i is missing (M is for “Missing”).

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

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

So, since we can put the function in M_i in one-to-one correspondence with all the functions from a set of size n to a set of size k+(n-1), the size of M_i is just the number of such functions, that is, (k+(n-1))^n.

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 M_1, since 1 is missing too. And this is why we can’t simply subtract each of the M_i 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!

About Brent

Assistant 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.

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.