Combinatorial Proof: Find dn for n≥2

  • Thread starter silvermane
  • Start date
  • Tags
    Proof
In summary, the equation that the person is trying to solve is Dn = (n-1)Dn-1 +(n-1)Dn-2. This equation includes the terms Dn-1 and Dn-2. The person is trying to solve for the nth term, but they are having difficulty explaining how they derived the equation. They are looking for help from somebody who can help them explain why the equation works.
  • #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:
Physics news on Phys.org
  • #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...
 
  • #3
mrbohn1 said:
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
 

1. What is combinatorial proof?

Combinatorial proof is a mathematical technique used to prove a statement by counting the number of objects in two different ways. It is a useful tool in discrete mathematics and combinatorics.

2. How do you find dn for n≥2 using combinatorial proof?

To find dn for n≥2, you can use the technique of combinatorial proof by counting the number of ways to arrange a set of objects or the number of subsets of a given set.

3. What is the significance of using combinatorial proof?

Using combinatorial proof allows us to understand a mathematical statement in a more intuitive and visual way. It also provides a more rigorous and systematic approach to solving problems in combinatorics.

4. Can combinatorial proof be used to prove all mathematical statements?

No, combinatorial proof is only applicable to certain types of mathematical statements, particularly those involving counting and arrangement of objects.

5. Are there any limitations to using combinatorial proof?

One potential limitation of combinatorial proof is that it may not always provide the most efficient or elegant solution to a problem. It is important to consider other mathematical techniques and approaches when solving problems.

Back
Top