- #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: