IIT JEE , AIEEE Forum - Mathematics , Algebra

priyesh

hi pollp2 here is the derivation for which you requested

let's take this question of dearrangement & with the help of this we will prove the formula

Q) in how many ways can N letters be put in N envelopes so that no letter goes into its right envelope.

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 ^NC₁ ways to pick one person with the correct seat, ^NC₂ ways to pick two people with the correct seat, and so on.

Thus, the total number of derangements is this:

N ! - ^NC₁(N-1)! + ^NC₂ (N-2)! - ^NC₃ (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)ⁿ1/n! ) (this the the formula)

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 . (this is a shortcut method)

Hope the Method is Clear to ALL.

Cheers!

Ask & Discuss Questions with Community & Experts