1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorial Proof

  1. Mar 18, 2010 #1


    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

    (we have to find the equation... lol)

    3. 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: Mar 18, 2010
  2. jcsd
  3. Mar 18, 2010 #2
    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....
  4. Mar 18, 2010 #3


    User Avatar
    Gold Member

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook