Combinatorial Proof

[silvermane]

Homework Statement

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.

Homework Equations

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

 

[mrbohn1]

Could you tell us how you derived your equation? The way I see this, there are (n-1) choices of letter to give the first person. For each choice, then consider the person whose letter you gave that person. There are now (n-1) choices for this person as well. Similarly there are (n-2) choices for the person whose letter you gave to the second person, and so on. There are no choices for the last 2 people.

So I get that the number of ways to do this is: $$\frac{(n-1)(n-1)!}{2}$$. This doesn't fit your recurrence relation. You may be able to persuade me that I'm wrong however....

 

[silvermane]

Could you tell us how you derived your equation? The way I see this, there are (n-1) choices of letter to give the first person. For each choice, then consider the person whose letter you gave that person. There are now (n-1) choices for this person as well. Similarly there are (n-2) choices for the person whose letter you gave to the second person, and so on. There are no choices for the last 2 people.

So I get that the number of ways to do this is: $$\frac{(n-1)(n-1)!}{2}$$. This doesn't fit your recurrence relation. You may be able to persuade me that I'm wrong however....

Well, I talked to the professor and my recurrence relation IS correct. It is a recurrence relation not a formula for the nth term, so it must include Dn-1 and Dn-2 somewhere

Dn is the number of ways to distribute the letter to n people incorrectly, so say we have n-1 people get the wrong letter but the nth person, say David, gets a letter and returns it to that person, say Karen. Then she could have his letter or some other letter but gives it to him.

Case 1:Breaking it into the case where she could have his letter, we can say that Dn-2 is the number of ways to distribute the letters incorrectly to everyone except Dave and Karen. I can't really justify the (n-1), but i thought of it because there are (n-1) other people who have received a letter other than him. I just got lucky with that term and was correct.

Case 2:The second case is when she has a letter that isn't Dave's letter. This means that only she has received her own letter, and Dn-1 is the number of ways with which we can distribute the letters to everyone else incorrectly, including David since she gave him a letter that wasn't his. Once again, I can't exactly justify the (n-1).

Finally, by the Sum Rule, there are
Dn = (n-1)Dn-1 +(n-1)Dn-2
which is correct... I just need help with explaining. Thank you so much for your input, I was worried that no one knew or wanted to try to help lol