a bit of combinatorics: Derangement

A mail man had a tough job every morning. He had to deliver N letters to N destinations. One day, a lifetime of contemplation had struck him; he had always imagined how it would be like if everyone gets the wrong letter? He also wonder, in how many ways he could do this? 
Eg: for 3 letters 1,2,3 and with destinations A,B,C respectively, to send every letter wrongly he has 2 ways: 
2->A 
3->B 
1->C 

OR

3->A 
1->B 
2->C 

Can you help him solve the wonder of the beautiful mind of a post man? 

 Formal introduction: Derangement 
 A special class of permuting 1,2,3,4,5,...,n such that the number k is not in k-th position (or in other words, none of the letters are correctly delivered). 

This problem can be solved recursively: 
Suppose we are finding the total number of derangements of n numbers 1,2,3,...,n, let's call it D(n). 
Firstly, 1 must not be in position 1. So, let's say that it's in position k. We have 2 cases:

Case 1: the number k is at position 1. 
Essentially, 1 and k swap positions. In this setting, we are now left with the task of permuting n-2 numbers. This exactly is D(n-2). Since there are n-1 ways to choose k (from 2 to n), the total possibilities for case 1 is (n-1)*D(n-2). 

Case 2: the number k is not at position 1. 
This means that position 1 is occupied with some other number than k. This seems to be more complicated than case 1, but it's not. This is equivalent to our initial problem (where 1 cannot be in position 1, but instead of 1, we now have k), which is equal to finding total number of derangements of n-1 numbers, D(n-1). 

Therefore, D(n) = D(n-1) + (n-1)*D(n-2).