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