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

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 , or put another way, the number of one-to-one matchings between two different sets of size . 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 , that is,

.

The first thing I want to do is switch the direction of the summation. That is, everywhere we currently have I want to replace it with , and vice versa. So will switch places with , and will switch with , and so on. Ultimately we will still have the same values of , 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 at all.

Finally, note that (there are the same number of ways to choose things out of as there are to choose things to exclude), so we can write

.

## Functions

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

For this example I chose and . The blue dots on the left represent the set of size . The dots on the right represent the set of size : I made of them blue to emphasize that they “correspond” to the blue dots on the left, and the remaining “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, , 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 to , 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.

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

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.

I understand your approach. I also appreciate the use of different points of view for proving something.

Thanks for your blog !

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