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

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

5 Responses to A combinatorial proof: functions and matchings

Christophe BAL says:

October 2, 2019 at 4:54 pm

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).
- Brent says:
  
  October 3, 2019 at 5:26 am
  
  Yes, this proof was discussed in the comments on a previous post: https://mathlesstraveled.com/2019/08/31/a-combinatorial-proof-reboot/#comment-46083 I know of this proof, but I don’t really care about the theorem itself, my goal is just to show a fun example of a combinatorial proof.
  - Christophe BAL says:
    
    October 3, 2019 at 5:37 am
    
    I understand your approach. I also appreciate the use of different points of view for proving something.
    Thanks for your blog !
Christophe BAL says:

October 3, 2019 at 1:26 am

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.
Pingback: A combinatorial proof: counting bad functions | The Math Less Traveled

Comments are closed.