Derangements — find number of permutations where no element is in original position

Question

Find the number of ways to arrange $n$ distinct objects such that no object is in its original position (derangement). Compute $D_4$ and $D_5$ explicitly.

(JEE Advanced 2021, similar pattern)

Solution — Step by Step

Let $A_i$ = set of permutations where element $i$ IS in its original position. We want the number of permutations where NO element is in its original position:

D_n = n! - |A_1 \cup A_2 \cup \cdots \cup A_n|

By inclusion-exclusion:

|A_1 \cup \cdots \cup A_n| = \sum|A_i| - \sum|A_i \cap A_j| + \cdots + (-1)^{n+1}|A_1 \cap \cdots \cap A_n|

$|A_i|$ = permutations fixing element $i$ = $(n-1)!$ . There are $\binom{n}{1}$ such terms.

$|A_i \cap A_j|$ = permutations fixing both $i$ and $j$ = $(n-2)!$ . There are $\binom{n}{2}$ terms.

In general: $\binom{n}{k}(n-k)!$ for $k$ fixed elements.

D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n \binom{n}{n}(0)!

Since $\binom{n}{k}(n-k)! = \frac{n!}{k!}$ :

D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)

\boxed{D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}}

D_4 = 4!\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 24 \times \frac{3}{8} = \mathbf{9}

D_5 = 5!\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 120 \times \frac{11}{30} = \mathbf{44}

Why This Works

The formula is a direct application of inclusion-exclusion. We start with all $n!$ permutations and subtract those where at least one element is fixed. The alternating sum corrects for over-counting — permutations with two fixed points get subtracted twice, so we add them back, and so on.

As $n$ grows large, $D_n/n!$ approaches $e^{-1} \approx 0.368$ — so roughly 36.8% of all permutations are derangements, regardless of how large $n$ is. This is a surprising and elegant result.

The small values worth memorising: $D_1 = 0$ , $D_2 = 1$ , $D_3 = 2$ , $D_4 = 9$ , $D_5 = 44$ .

Alternative Method — Recurrence relation

Derangements satisfy two useful recurrences:

D_n = (n-1)(D_{n-1} + D_{n-2})

D_n = nD_{n-1} + (-1)^n

The first says: element 1 goes to position $j$ ( $(n-1)$ choices). Then either element $j$ goes to position 1 (and the remaining $n-2$ elements form a derangement: $D_{n-2}$ ), or element $j$ does NOT go to position 1 (equivalent to a derangement of $n-1$ elements: $D_{n-1}$ ).

For JEE, the derangement formula is frequently tested in disguised forms: “letters in wrong envelopes,” “hats returned to wrong people,” “matching problems.” Whenever a problem says “no element in its correct position,” think derangement. The formula $D_n = n!(1 - 1 + 1/2! - 1/3! + \cdots)$ can be quickly computed for small $n$ .

Common Mistake

Students sometimes confuse $D_n$ with “number of permutations with at least one element NOT in its position” — which is almost all permutations ( $n! - 1$ for $n \geq 2$ ). Derangements require that ALL elements are displaced, not just some. The question phrasing matters: “no element in its original position” means derangement, while “at least one element displaced” is a different (and much simpler) problem.

Question

Solution — Step by Step

Why This Works

Alternative Method — Recurrence relation

Common Mistake

Try These Next