Derangements

Rarely Tested

Derangements

## Definition / Concept

A derangement is a permutation in which no object occupies its original position.

The number of derangements of $$n$$ distinct objects is denoted by:

$$!n$$

## Formula

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

Equivalently:

$$!n=n\cdot!(n-1)+(-1)^n$$

## Usage

- Used in permutation problems where every object must be displaced from its original position.

Question 1

Let $$S = \{x \in \mathbb{N} : 1 \leq x \leq 9\}$$ be a set of the first $$9$$ natural numbers. A bijective function $$f: S \to S$$ is constructed randomly to form a sequence of elements denoted by $$(a_1, a_2, a_3, \dots, a_9)$$, where $$a_i = f(i)$$ for each $$i \in S$$. Let $$E_1$$ be the event that the sequence forms a complete derangement of the set $$S$$, such that $$f(i) \neq i$$ for all $$i \in S$$. Let $$E_2$$ be the event that all prime numbers in the domain map to prime numbers in the codomain, satisfying the structural constraint $$f(\{2, 3, 5, 7\}) = \{2, 3, 5, 7\}$$. If $$N$$ represents the total number of unique bijective functions $$f(x)$$ that simultaneously satisfy the conditions for both events $$E_1$$ and $$E_2$$, then the value of $$N$$ is:

Go back to topics

Join CAT 2026 course by 5-Time CAT 100%iler

Start your IIM journey with the right preparation and crack CAT 2026.