What Are Derangements ?
Answer : Arranging N items in N places such that no item gets the right place.
Lets take the example of n letters and N envelopes. The example problem is when N = 5 .
The problem can also be like N people with n seats etc ....
We have N letters and envelopes. The Letters can be put in the N envelopes in N! ways . We want to count the Number of "Derangements" ( The no. of ways that no letter goes into right envelope ) . To do this begin with N! and subtract off the ones where there is a match.
How many arrangements are there with 1 letter and envelope ? Well the rest
(N-1 ) letters can be arranged in (N-1)! ways and hence (N-1)! arrangements.
There are a similar number of arrangements with letter 2 in envelope 2, etc
So we?ll subtract all those off. But then we?ve subtracted many arrangements more than once. Some of the arrangements have the correct letters in both envelopes 1 and 2, and we subtracted that arrangement twice.
How many arrangements have letters 1 and 2 in the correct envelopes ? Well, there are (N-2) remaining letters whic can be arranged in (N-2)! ways.
We need to add in all of those, then subtract off all the cases where there are at least 3 letters in the right envelopes then add in the cases with 4, etc
So there are NC1 ways to pick one person with the correct seat, NC2 ways to pick two people with the correct seat, and so on.
Thus, the total number of derangements is this:
N ! - NC1 (N-1)! + NC2 (N-2)! - NC3 (N-3)! ..............
= N! - N(N-1)! / 1! + N(N-1)(N-2)! / 2! + N(N-1)(N-2)(N-3)! / 3! +.......
= N!( 1- 1/1! + 1/2! - 1/3! +..................+(-1)n 1/n! )
By substituting the value N = 5 , We get the Answer as 44 .
For Large numbers the sequence 1 - 1/1!+ ........... turns out to be e-1 . So just divide the N! by e . Here too By dividing we get
5! / 2.71828 = 44.1455
Since Number of ways is not fraction we take the answer as 44 .
So Next time You see such problem , then straightaway divide N! / e .
Back to Community Shelf
Awaiting Review for Nickels![[Post New]](/templates/default/images/icon_minipost_new.gif){kind=icon}
153
1
