Suppose that you have n letters addressed to n distinct people. Let dn be the number of ways to deliver the letters to the n people so that everyone receives exactly one letter, but nobody receives the letter that is addressed to them. Find a recurrence relation satisfied by dn for n ≥ 2. Justify your recurrence relation using combinatorial reasoning. Find specific values for d0 and d1.
(we have to find the equation... lol)
The Attempt at a Solution
So far, I've derived the equation,
Dn = (n-1)D[n-2] + D[n-1](n-1)
I am sure that it is correct, however I am completely STUCK in the explanation. I know how to explain it normally, but stumble horribly when I try it out mathematically. Please help with the explanation, and let me know if the formula looks good or not. Thank you so much in advance!
Note: [ ] means it's a subscript, ( ) means it's multiplied.