Derivation of Derangement formula

This question comes from my unsuccessful attempt to solve

http://www.mathhelpforum.com/math-he...-problems.html

(Reason im posting a new thread: dont want to hijack the other one with my own questions).

The question was:

"there are n letters and n addressed envelopes. Letters are placed randomly in envelopes. find the probability that at least 1 letter goes in the correct envelope"

The correct answer is

Quote:

Originally Posted by

**Plato** The number of derangements on $\displaystyle n$ items is $\displaystyle D_n = n! \cdot \sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}} \approx \frac{{n!}}{e}$.

The probability that at least one term of a permutation remained fixed is $\displaystyle 1 - \frac{{D_n }}{{n!}} \approx \frac{{e - 1}}{e} = {0.63212}$.

But i thought it was

Quote:

Originally Posted by

**SpringFan25** you can do this with a tree diagram, where each branch has 2 possible outcome (correct, not correct).

I wouldn't try and draw the whole thing, but its good to ahve in the back of your head.

**Step 1:**

Find the probability that no paycheck is in the correct envelope:

P(0) = $\displaystyle \frac{n-1}{n} \times \frac{n-2}{n-3} \times .... \frac{1}{2}$

$\displaystyle = \frac{(n-1)(n-2)....2}{n (n-1) (n-2)....2 \times 1}$

$\displaystyle =\frac{1}{n}$

**Step 2:**

P(at least 1) = 1-P(0)

$\displaystyle =\frac{n-1}{n}$

Check for n=3:

$\displaystyle \frac{3-1}{3} = \frac{2}{3}$, which you said was correct

So, i have 2 questions:

1) What's the conceptual mistake in my approach

2) Is there a derivation of the subfactorial function somewhere?