# Permutation Problem

• October 20th 2008, 07:30 AM
skyskiers
Permutation Problem

There are 8 envelops and 8 corresponding letters. Find the probability that :-
a) At least 2 letters go to the wrong envelops.
b) None of the letters go in to the right envelop.

• October 20th 2008, 08:35 AM
Plato
The answer to the b part is $\approx \frac{1}{e}$
I bet you wonder why. Look at the following webpage.
Derangement -- from Wolfram MathWorld
• October 20th 2008, 01:47 PM
Soroban
Hello, skyskiers!

Quote:

There are 8 envelopes and 8 corresponding letters.
There are: . $8! = 40,\!320$ possible outcomes.

Quote:

Find the probability that:

a) At least 2 letters go to the wrong envelopes.

This is a bit of a "trick question".

Is there a way for exactly one letter to be in the wrong envelope?

Imagine . . . the other 7 letters are in the right envelopes.
. . Can the 8th one go into a wrong envelope? . . . No.

So it is impossible for exactly one letter to be misplaced.
That is, if any are misplaced, there will be at least two misplaced.

There is exactly one way for the letters be matched to their envelopes.
. . $P(\text{all correct}) \:=\:\frac{1}{40,\!320}$

The rest of the time, there will be at least 2 misplaced.

Therefore: . $P(\text{at least 2 misplaced}) \;=\;1-\frac{1}{40,\!320} \;=\;\frac{40,\!319}{40,\!320}$

Quote:

b) None of the letters go in to the right envelope.
This is a messy problem and has an obscure solution.

An arrangement of $n$ objects in which no object is in its proper position
. . is a derangement of the $n$ objects.

We want the number of derangements of 8 objects: $d(8)$

It can be found by: . $d(8) \;=\;(Q-1)^8\;\;\text{ where }Q^n = n!$
. .
Imagine . . . an exponent becomes a factorial!

We have: . $(Q-1)^8 \:=\:Q^8 - 8Q^7 + 28Q^6 - 56Q^5 + 70Q^4 - 56Q^3 + 28Q^2 - 8Q + 1$

. . . . . . . . . . . . . $=\;8! - 8(7!) + 28(6!) - 56(5!) + 70(4!) - 56(3!) + 28(2!) - 8(1!) + 1$

. . . . . . . . . . . . . $= \;40,\!320 - 40,\!320 + 20,\!160 - 6,\!720 + 1,\!680 - 336 + 56 - 8 + 1$

. . . . . . . . . . . . . $= \;14,\!833$

Therefore, the probability is: . $\frac{14,\!833}{40,\!320} \;=\;\frac{2,\!119}{5,\!760}$

• October 20th 2008, 09:22 PM
skyskiers
Theres only 1 thing I can say....

You guys are just amazing....awesome..

Thx