Could someone check out this combinatorial proof? Thanks.

Let

be the number of derangements of an n-set. Define

and note

a) Give a combinatorial proof:

for

.

How many derangements of an n-set are there?

One way to count would be

.

Another way is to consider the n-set by separating out the n-1 numbers greater than 1, one at a time.

Start with 2. There are

derangements of the n-1 numbers in the n-set excluding the number 2. If we pre-pend the number 2 to the beginning of these derangements, we will still get

derangements because the 2 in the first position will not cause any of the numbers to be “fixed”. Now consider the next number in the n-set, 3. We can proceed the same as we did with the number 2 and there will again be

derangements with the number 3 pre-pended to the derangement. In fact, there will be n-1 such derangements. But notice that none of these derangements will have 1 in the second position of the sequence after the numbers have been pre-pended. That is because after we remove the number from the n-set and take the derangement of the n-1 numbers left, 1 can never be in the first position of that derangement. So, if we now go through the same steps again by removing 1 along with n-1 numbers, we can then take the derangements of the n-2 numbers left. Start with 21 and pre-pend 21 to the derangements of the n-2 numbers left just as we did with the single numbers. Each of these derangements will have

derangements and there will be n-1 of these derangements. When we add the second group of derangements to the first group of derangements it is clear that we now have all the derangements of [n]. Therefore we have proved that

for