# Thread: Combinatorial proof of derangement identity

1. ## Combinatorial proof of derangement identity

Could someone check out this combinatorial proof? Thanks.

Let $\displaystyle D_{n}$ be the number of derangements of an n-set. Define $\displaystyle D_{0}=1$ and note$\displaystyle D_{1}=0.$

a) Give a combinatorial proof: $\displaystyle D_{n}=(n-1)(D_{n-1}+D_{n-2})$ for $\displaystyle n\geq2$.

How many derangements of an n-set are there?

One way to count would be $\displaystyle D_{n}=n!\sum_{j=0}^{n}\frac{(-1)^{j}}{j!}$.

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 $\displaystyle D_{n-1}$ 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 $\displaystyle D_{n-1}$ 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 $\displaystyle D_{n-1}$ 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 $\displaystyle D_{n-2}$ 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 $\displaystyle D_{n}=(n-1)(D_{n-1}+D_{n-2})$ for $\displaystyle n\geq2.$

2. Another way to approach could be

Ignore the last (nth) element.
The remaining (n-1) elements can be de-arranged in D(n-1) ways, once you do that the nth element can interchange place with any of the (n-1) element to give you a de-arrangement of n elements.
Also, out of the (n-1) element we can have an element which holds its poisition, say element 'i'. Other element (remaining (n-2) elements) can be de-arranged in D(n-2) ways. Once this is done to get de-arrangement of 'n' elements you just interchange positions of ith and nth element. Now, i can take values from 1 to (n-1).

You can see immdiately that no more than 1 of the (n-1) elementss can hold its position. So above two exhaust all the cases for D(n). Hence

D(n) = (n-1).D(n-1) + (n-1)D(n-2)

3. Thank you so much for your advice. I really just learned combinatorial proofs in the last month, so I am very encouraged that my proof is not wrong. I have a long way to go to make them concise and totally solid, but this is very encouraging.

4. I actually haven't checked your proof please. Actually couldn't really follow you line of argument but it seems wrong to me.

5. Originally Posted by oldguynewstudent
Could someone check out this combinatorial proof? Thanks.

Let $\displaystyle D_{n}$ be the number of derangements of an n-set. Define $\displaystyle D_{0}=1$ and note$\displaystyle D_{1}=0.$

a) Give a combinatorial proof: $\displaystyle D_{n}=(n-1)(D_{n-1}+D_{n-2})$ for $\displaystyle n\geq2$.

How many derangements of an n-set are there?

One way to count would be $\displaystyle D_{n}=n!\sum_{j=0}^{n}\frac{(-1)^{j}}{j!}$.

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 $\displaystyle D_{n-1}$ 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 $\displaystyle D_{n-1}$ 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 $\displaystyle D_{n-1}$ 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 $\displaystyle D_{n-2}$ 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 $\displaystyle D_{n}=(n-1)(D_{n-1}+D_{n-2})$ for $\displaystyle n\geq2.$
Looks fine to me!