A combinatorial proof: functions and matchings

We’re trying to prove the following equality (see my previous post for a recap of the story so far):

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

In particular we’re trying to show that the two sides of this equation correspond to two different ways to count the same set of mathematical objects. We already know that the right-hand side counts the number of permutations of a set of size n, or put another way, the number of one-to-one matchings between two different sets of size n. Somehow, then, we need to show that the left side of the equation is just a complicated way to count the same thing.

Cosmetic surgery

Let’s call the left-hand side of the equation S, that is,

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

The first thing I want to do is switch the direction of the summation. That is, everywhere we currently have i I want to replace it with n-i, and vice versa. So 0 will switch places with n, and 1 will switch with n-1, and so on. Ultimately we will still have the same values of i, just in the reverse order. Of course, the order in which we add up a bunch of things doesn’t matter (since addition is commutative), so this won’t change the value of S at all.

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

Finally, note that \binom{n}{n-i} = \binom{n}{i} (there are the same number of ways to choose n-i things out of n as there are to choose i things to exclude), so we can write

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

Functions

When i = 0, S involves the term (k+n)^n. Let’s think about what that counts. I explained in a previous post that a^b is the number of functions from a set of size b to a set of size a (as a reminder, this is because the function gets to independently choose where to map each input value—so there are b choices for each of the a inputs, for a total of b \cdot b \cdot \dots \cdot b = b^a choices). So let’s draw a typical function from a set of size n to a set of size k+n:

For this example I chose n = 5 and k = 3. The blue dots on the left represent the set of size n. The dots on the right represent the set of size k+n: I made n of them blue to emphasize that they “correspond” to the blue dots on the left, and the remaining k “extra” dots are orange.

The arrows indicate what the function does. To be a valid function, it has to be defined for each element of the input set; that is, in the picture, there has to be exactly one arrow coming out of each dot on the left. However, the arrows can go anywhere. Note that in the example above, one arrow points to an orange dot, and two other arrows point the same blue dot (we could say they “collide”).

Some of these functions are actually matchings between the blue dots on the left and right, that is, every arrow points to a blue dot, and none of the arrows collide. For example:

We already know that the right-hand side of the equation, n!, is the number of such matchings. And we’re going to show that the left-hand side of the equation is what you get if you start with all the possible functions from n to n+k, and then subtract the ones that aren’t matchings. Of course, these should give you the same result! If you like, between now and my next post, you can try to work out the details for yourself.

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.

5 Responses to A combinatorial proof: functions and matchings

  1. Christophe BAL says:

    Hello.
    I don’t know if the following remark has already be given but there is a rather simple algebra proof after noticing that the process works more generally with polynomials X, X+1, X+2, … , X+n. here is a link to SageCell showing that :
    https://sagecell.sagemath.org/?z=eJwlj0sOwyAMRNfhFO4OyEdB7SpSbsANUBZIcVsk6iJClBy_Jt3ZM_OsMcEMDyG24nPhMXtaAxVpxg7MqPVdCWFZd_KEFoLSmuD5zRAgUA2_UBIbRi1CHO8QESKStApuM5hJNITHhbPdXFwHGEuFkfYPZl9QWjf1ZlGcvuKDTwlpZTm0ZoG-AtyiqXeq7yY-lnHbYy1s3cirSLm2_qsDnonfkEr9AM9DPdo=&lang=sage&interacts=eJyLjgUAARUAuQ==

    Then it is easy to write a purely algebraic proof. I will do that this weekend (it will be in french but I could post it there if you want).

  2. Christophe BAL says:

    The main steps of the proof are the following ones.
    1) We start with the list [P(X) , P(X+1) , P(X+2) , … , P(X+n)] with a polynomial P.
    2) The next list is [P(X+1) – P(X) , P(X+2) – P(X+1) , P(X+3) – P(X+2) , … , P(X+n) – P(X+n-1)] that is [Q(X) , Q(X+1) , Q(X+2) , … , Q(X+n-1)] with Q(X) := P(X+1) – P(X).
    3) If P(X) = a_n X^n + … then P(X+1) – P(X) = n a_n X^{n-1} + … because (X+1)^k – X^k = k X^{k-1} + …
    An easy recurrence gives the result by noting the decrease of the degree of the polynomials involved at each iteration.
    The advantage of this proof is that it show where the trick comes from.

  3. Pingback: A combinatorial proof: counting bad functions | The Math Less Traveled

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.