Making our equation count

[This is post #4 in a series; previous posts can be found here: Differences of powers of consecutive integers, Differences of powers of consecutive integers, part II, Combinatorial proofs.]

We’re still trying to find a proof of the equation

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

which expresses the fact that a certain arithmetic procedure always seems to result, strangely enough, in the factorial of $n$ . Last time I introduced the idea of using a combinatorial proof, and gave a simple example involving a binomial coefficient identity.

In order for this idea to yield any fruit, we need a way to interpret the various pieces of the equation as counting something. Let’s go over the pieces one by one and discuss some ways to interpret them combinatorially.

Factorial, permutations, and matchings

Let’s start with the right-hand side, $n!$ . This one is not too hard: $n!$ counts the number of permutations of $n$ objects, that is, the number of different ways to take $n$ distinct objects and arrange them in an ordered list. Why is that? Well, there are $n$ objects we could choose to put first; once we’ve made that choice, there are $n-1$ remaining objects we could choose to go second; then $n-2$ choices for the third object, and so on, for a total of $n (n-1) (n-2) \dots 1 = n!$ choices. For example, here are the $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ different permutations of size $4$ :

However, there’s another way to think about permutations which will come in handy later. Namely, we can think of a permutation as a matching between two sets of size $n$ . You know, like those puzzles that give two side-by-side lists and say “draw a line matching each cartoon character with their favorite cheese!” (…or whatever). Like this:

Here we have a matching between two sets of size $6$ . Each dot on the left is matched with exactly one dot on the right, and vice versa.

Why are matchings another way of thinking about permutations? First, it’s not too hard to see that there are also $n!$ matchings between two sets of size $n$ : we have $n$ possible choices of what to match the first element with; then there are $n-1$ choices left over for what to match the second element with, and so on.

But we can also see a correspondence between permutations and matchings more directly. Start by labeling the dots on the left of a matching with consecutive numbers:

Now, imagine each number “traveling” along the corresponding red edge until it reaches the dot on the other side. Like this:

See how the $1$ traveled down the steep edge to end up at the fourth dot from the top; the $2$ traveled across the horizontal edge to stay in the same position; the $3$ traveled up to the top; and so on.

What we get out is a list of the numbers from 1–6 in some order; in this example we get $3,2,5,1,6,4$ . In other words, we can view a matching as a little physical machine for taking a list of objects and putting them into some particular order.

Here are all the permutations of size $4$ again, this time visualized as matchings.

Now, at this point I am very tempted to go off on a tangent exploring group theory, symmetry groups, and all sorts of other stuff, but I shall restrain myself (for now!).

Binomial coefficients

Another piece of the equation is the binomial coefficient $\binom n i$ . But of course we already know what binomial coefficients count— $\binom n i$ is the number of ways to choose $i$ things out of $n$ , that is, the number of size- $i$ subsets of a size- $n$ set. (I also talked about this last time.)

Exponentiation and functions

What about $(k+i)^n$ ? What does that count? It turns out that exponentiation corresponds to counting functions: in particular, $b^a$ is the number of functions from a set of size $a$ to a set of size $b$ . Why is that? Well, for each of the $a$ elements of the domain, we have $b$ choices for where a function could send it, and each of these choices is independent—so the total number of choices is $b \cdot b \cdot \dots \cdot b = b^a$ .

For example, here are all of the $3^3 = 27$ functions from a size- $3$ set to a size- $3$ set:

Hmmm… this looks familiar! Note that some of these functions are matchings, and some aren’t. Perhaps you’re starting to get an inkling now why I introduced the idea of permutations as matchings…

All the pieces are almost in place now. The one piece of the equation we still haven’t yet talked about is that mysterious $(-1)^{n-i}$ . It certainly doesn’t make sense to interpret that as the number of functions from a set of size $n-i$ to a “set of size negative one”, because of course there is no such thing as a set with a negative size. So how can we interpret it combinatorially? The answer lies in something called the Principle of Inclusion-Exclusion (or PIE for short), which will be the subject of my next post!

3 Responses to Making our equation count

akismet-457375c2686d2ce6aa9740f00ee2f8f4 says:

March 11, 2012 at 1:25 am

Just lovely. I can’t wait to share this with teachers when you do the last part.
Pingback: Travels in a Mathematical World
Pingback: How to explain the principle of inclusion-exclusion? | The Math Less Traveled

Comments are closed.