calendarBack
Quant

/

Modern Maths

/

Permutations & Combinations
ALL MODULES

CAT 2025 Lesson : Permutations & Combinations - Derangement

bookmarked

5. Derangement

Derangements of
r\bm{r} objects is when each of these objects are misplaced or wrongly assigned.

Number of Derangements
== D(r)\bm{(r)} = r!×(111!+12!13!+...)r! \times \left( 1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + ... \right)

In cases where there is a total of
n\bm{n} objects, and r\bm{r} of them are misplaced or wrongly assigned, we first select the rr elements in nCr^{n}C_{r} ways and then derange them.

Number of such derangements
== nCr×D(r)=^{n}C_{r} \times D(r) = nCr×r!×(111!+12!13!+...)^{n}C_{r} \times r! \times \left( 1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + ... \right)

It's not too hard to derive the derangements. However, we recommend you to memorise the following.

D(1)=0(1) = 0 D(2)=1(2) = 1 D(3)=2(3) = 2 D(4)=9(4) = 9 D(5)=44(5) = 44

Furthermore, derangements can be derived as follows.
When
nn is odd, D(n)=((n) = (D(n1)×n)1(n - 1) \times n) - 1
When
nn is even, D(n)=((n) = (D(n1)×n)+1(n - 1) \times n) + 1

Using this we can derive D
(6)=44×6+1=265(6) = 44 \times 6 + 1 = 265; D(7)=265×71=1854(7) = 265 \times 7 - 1 = 1854 and so on.

Example 37

What is the number of ways in which 66 letters can be put into 66 envelopes, such that exactly 22 of the letters get into the correct envelopes?

Solution

From 66 letters, 44 need to be selected and put into incorrect envelopes, i.e. deranged.

Number of ways
== 6C4×^{6}C_{4} \times D(4)=15×9=135(4) = 15 \times 9 = 135

Answer:
135135


Loading...Loading Video....