• Support PF! Buy your school textbooks, materials and every day products Here!

Combinatorial Proof

  • Thread starter silvermane
  • Start date
  • #1
silvermane
Gold Member
117
0

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.
 
Last edited:

Answers and Replies

  • #2
97
0
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: [tex]\frac{(n-1)(n-1)!}{2}[/tex]. This doesn't fit your recurrence relation. You may be able to persuade me that I'm wrong however....
 
  • #3
silvermane
Gold Member
117
0
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: [tex]\frac{(n-1)(n-1)!}{2}[/tex]. 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
 

Related Threads for: Combinatorial Proof

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
6
Views
870
Replies
1
Views
3K
  • Last Post
Replies
1
Views
2K
Replies
3
Views
3K
Top