Derivation of Derangement formula

**SpringFan25** · June 6th 2010, 10:12 AM

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

Originally Posted by Plato

The number of derangements on $n$ items is $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 $1 - \frac{{D_n }}{{n!}} \approx \frac{{e - 1}}{e} = {0.63212}$ .

But i thought it was

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) = $\frac{n-1}{n} \times \frac{n-2}{n-3} \times .... \frac{1}{2}$

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

$=\frac{1}{n}$

Step 2:
P(at least 1) = 1-P(0)
$=\frac{n-1}{n}$

Check for n=3:
$\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?

**Moo** · June 6th 2010, 10:38 AM

Hello,

I'll try to explain with an example.

Your reasoning was that you first calculate the probability that the first letter doesn't go in its proper envelope (probability of (n-1)/n)).
Then, same probability for the second, etc...

But now consider this situation : you put the first letter in the envelope that is supposed to contain the second letter. Then the probability of putting the second letter in a wrong envelope is 1, because its 'correct' envelope is already taken !

And you have this situation every time you have to put a letter in an envelope... this is why you have to use derangements

**Plato** · June 6th 2010, 10:46 AM

Originally Posted by SpringFan25

1) What's the conceptual mistake in my approach

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

Did you read the webpage that I posted?

Do you understand the inclusion/exclusion rule?

**Archie Meade** · June 6th 2010, 10:51 AM

Originally Posted by SpringFan25

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

But i thought it was

So, i have 2 questions:
1) What's the conceptual mistake in my approach ?

Hi SpringFan25,

also consider that....
at the beginning, there are n-1 ways to put a wrong paycheck in envelope number 1.
However, there will not always be n-2 choices for the 2nd, n-3 for the 3rd etc.

In the case of 4 envelopes,
if we place P3 in E1 followed by P1 in E2, then we only can place P4 in E3 and P2 in E4 to have all paychecks in incorrect envelopes.

However, if we place P3 in E1 and P4 in E2, then we can have P2 in E3 and P1 in E4 or P1 in E3 and P2 in E4.

**SpringFan25** · June 6th 2010, 10:52 AM

Moo/AM,

thanks, that takes care of question 1

Plato
i did read the page and i dont understand that rule

**SpringFan25** · June 6th 2010, 10:59 AM

ok, now i understand the inclusion/exclusion rule (barely).

I'll see if i can apply it to this problem

cya in 15 years

**SpringFan25** · June 6th 2010, 12:55 PM

This is going to get messy because they dont actually teach set theory to economists ^^.

I proved the inclusion/exclusion rule but i haven't been able to apply it to this problem.

I started thinking on these lines:

Problem: n tokens, n boxes, find number of combinations where no token is in the right box

Define $S_i$ as the set of combinations where token i is not in the correct box

Define $T_i$ as the set of combinations where i tokens are not in the correct box. (this is just a shorthand, any set T can be constructed from operations with S).

I tried to apply the inclusion/exclusion rule as follows:

$D(n) = |T_n| = |S_1 \cap S_2 \cap S_3 ..... \cap S_n|$

$= |S_1| + |S_2| + |S_3| + ...$
$-1 * |T_2|$
$+1 *|T_3|$

..etc

However, i was not able to find
$|S_1| + |S_2| + |S_3| .....$

edit incorrect reasoning fixed
Trying to find $|S_1|$ i thought:
"token 1 in the wrong place, all other tokens in the right place"

$|S_1|$ = (ways of having n-1 tokens in the right place) * (ways of having token 1 in the wrong place if the others are correct)
=0
!!

Am i going in the wrong direction?

**Plato** · June 6th 2010, 01:15 PM

$S_1$ token 1 is in the right place no matter where the others are.

$\left| {S_1 \cup S_2 \cup S_3 } \right| = \left| {S_1 } \right| + \left| {S_2 } \right| + \left| {S_3 } \right| - \left| {S_1 \cap S_2 } \right| - \left| {S_1 \cap S_3 } \right| - \left| {S_3 \cap S_2 } \right| + \left| {S_1 \cap S_2 \cap S_3 } \right|$
$\begin{gathered}<br /> + \hfill \\<br /> \left| {S_k } \right| = 2,\;\left| {S_k \cap S_j } \right| = 1,\;\& \;\left| {S_1 \cap S_2 \cap S_3 } \right| = 1 \end{gathered}$

$\left| {S_1 \cup S_2 \cup S_3 } \right| = 3 \cdot 2 - 3 \cdot 1 + 1 = 4$

**SpringFan25** · June 6th 2010, 01:28 PM

sorry, i changed the notiation just before i posted and confused myself.

$S_1$ was the set of combinations where token 1 is in the wrong place

So i try to find $|S_1|$ as

"token 1 in the wrong place, all other tokens in the right place"

$|S_1|$ = (ways of having n-1 tokens in the right place) * (ways of having token 1 in the wrong place if the others are correct)
=0

which i figure means i am probably going in completely the wrong direction as the problem will start to look like:

$0 + 0 + 0 + ...$
$-1 * |T_2|$
$+1 * |T_3|$

And when i come to find $|T_2|$ i would say
$|T_2|$ = " combis where 2 tokens are correct, n-2 wrong"

= $^nC_2 * D(n-2)$

which is again going heading towards a recursive answer, if any at all.

**Plato** · June 6th 2010, 01:42 PM

None is in the correct place is the opposite of at least one in the right place.
So a derangement is the opposite if at least one in the right place.
$|A\cup B \cup C \cup D|$ counts the number of ways that at least one of $A,~B,~C,\text{ or }D$ is in the correct place.
That number $4\cdot 3!-6\cdot2!+4\cdot 1!-1\cdot 0!=15$ .
Take that from $4!$ and you have the derangement of four items.

Thread: Derivation of Derangement formula

LinkBack

Thread Tools

Display

Derivation of Derangement formula

Similar Math Help Forum Discussions

derivation of the Quadratic Formula

axisymmetric jet formula derivation

axisymmetric jet formula derivation

Need the derivation of area formula of a segment

[SOLVED] Derivation of formula using calculus?

Search Tags