Its a pretty standard problem. Solution for n is here (dont mind my mistakes, typed very fast)
We have N letters and N 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! ) (this the the formula)
Win We Must
Locked
