Derangement: Concepts, Definition & Solved Examples

What is Derangement?

Derangement is a special concept in permutations where objects are rearranged in such a way that none of them remains in its original position. It is one of the most interesting topics in combinatorics because it combines counting techniques, probability, and logical reasoning. Derangement problems frequently appear in advanced mathematics, probability theory, cryptography, and competitive examinations.

Derangement Meaning in Simple Words

In simple terms, a derangement occurs when every object is placed in the wrong position.

For example, suppose three students A, B, and C are assigned seats 1, 2, and 3 respectively.

Original arrangement:

A → 1

B → 2

C → 3

A derangement could be:

A → 2

B → 3

C → 1

Since no student occupies the assigned seat, this arrangement is a derangement.

Definition of Derangement

A derangement is a permutation of a set of objects in which no element appears in its original position.

If there are $n$ distinct objects, the number of derangements is denoted by:

$!n$

or

$D_n$

For example:

• $D_2=1$

• $D_3=2$

• $D_4=9$

Derangements are sometimes called complete permutations.

Why Derangement is Important

Derangement plays an important role in combinatorial mathematics and probability.

Its importance includes:

• Understanding advanced counting techniques.

• Solving matching and assignment problems.

• Studying probability distributions.

• Designing cryptographic systems.

• Developing algorithms in computer science.

Derangement problems are also common in JEE, Olympiads, CAT, GATE, and university-level mathematics.

Real-Life Examples of Derangement

Derangement appears naturally in many practical situations.

Secret Santa

Everyone gives a gift, but nobody receives their own gift.

Exam Seating

Students are assigned seats different from their allotted seats.

Letter-Envelope Problems

Letters are placed in envelopes such that no letter goes into its correct envelope.

Matching Games

No participant is matched with the original assigned partner.

These situations can all be analyzed using derangements.

Basics of Derangement

Before studying formulas, it is important to understand how derangements relate to permutations.

Understanding Permutations and Derangements

A permutation is any arrangement of objects.

For example, the permutations of A, B, and C are:

ABC, ACB, BAC, BCA, CAB, CBA

A derangement is a special type of permutation where no object remains in its original position.

Thus:

Every derangement is a permutation, but not every permutation is a derangement.

Fixed Points in a Permutation

A fixed point is an element that remains in its original position after a permutation.

For example:

Original arrangement:

ABCD

Permutation:

ABDC

Here:

• A remains fixed.

• B remains fixed.

Therefore, this permutation contains two fixed points.

A derangement contains no fixed points.

What Makes a Permutation a Derangement?

A permutation becomes a derangement only when:

• Every element moves.

• No element remains in its original position.

• The number of fixed points equals zero.

For example:

Original:

ABC

Derangement:

BCA

Here:

• A is not in position 1.

• B is not in position 2.

• C is not in position 3.

Hence it is a derangement.

Difference Between Permutation and Derangement

History of Derangement

Derangement has a rich history dating back several centuries.

Origin of the Derangement Problem

The derangement problem originated from practical matching problems involving misplaced objects.

Mathematicians became interested in determining how many arrangements were possible when every object had to be misplaced.

This led to one of the earliest applications of the inclusion-exclusion principle.

The Hat-Check Problem

The most famous derangement example is the Hat-Check Problem.

Suppose:

• $n$ guests attend a party.

• Each guest checks a hat.

• The hats are returned randomly.

The question is:

How many ways can the hats be returned so that nobody receives their own hat?

This classic problem introduced the concept of derangements.

Contributions of Pierre Raymond de Montmort

The French mathematician Pierre Raymond de Montmort studied the hat-check problem extensively in the early 1700s.

His work helped establish the modern theory of derangements and inclusion-exclusion counting.

He was among the first mathematicians to derive formulas for derangement numbers.

Evolution of Derangement Theory

Over time, derangement theory expanded into:

• Combinatorics

• Probability

• Computer science

• Cryptography

• Operations research

Today, derangements remain an important topic in advanced mathematics.

Derangement Formula

A direct formula exists for calculating the number of derangements.

Standard Derangement Formula

The number of derangements of $n$ objects is:

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

This formula is derived using the inclusion-exclusion principle.

Meaning of Variables in the Formula

In the formula:

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

• $D_n$ = Number of derangements

• $n$ = Total objects

• $n!$ = Total permutations

The alternating series adjusts for fixed positions.

Derangement Notation $!n$

Derangements are commonly written as:

$!n$

Examples:

• $!1=0$

• $!2=1$

• $!3=2$

• $!4=9$

• $!5=44$

This notation is widely used in combinatorics.

Approximation Formula Using $e$

For large values of $n$:

$D_n\approx\frac{n!}{e}$

where:

$e\approx2.71828$

This approximation becomes extremely accurate as $n$ increases.

Derivation of the Derangement Formula

The standard derangement formula is obtained using the inclusion-exclusion principle.

Introduction to the Inclusion-Exclusion Principle

The inclusion-exclusion principle counts arrangements while removing overcounted cases.

It is frequently used when several restrictions exist simultaneously.

Counting Total Permutations

For $n$ objects:

Total permutations:

$n!$

This count includes arrangements with fixed positions.

Eliminating Fixed Positions

Suppose:

$A_i$

represents the event that the $i^{th}$ object remains fixed.

Using inclusion-exclusion:

• Subtract arrangements with one fixed point.

• Add arrangements with two fixed points.

• Subtract arrangements with three fixed points.

Continue until all cases are considered.

Deriving the General Derangement Formula

Applying inclusion-exclusion yields:

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

This becomes the standard derangement formula.

Recurrence Relation for Derangements

Derangements can also be computed recursively.

Derangement Recurrence Formula

The recurrence relation is:

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

for:

$n\ge2$

with:

$D_0=1,\quad D_1=0$

Proof of the Recurrence Relation

Consider object 1.

It can move to any of the remaining:

$(n-1)$

positions.

Two possibilities arise:

• A swap occurs.

• A longer cycle occurs.

Combining both cases leads to:

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

Computing Derangements Using Recursion

Using:

$D_0=1$

$D_1=0$

we obtain:

$D_2=1$

$D_3=2$

$D_4=9$

$D_5=44$

and so on.

Advantages of the Recurrence Method

The recurrence relation:

• Avoids lengthy calculations.

• Is efficient for programming.

• Simplifies computation for large values of $n$.

Properties of Derangements

Derangement numbers exhibit several interesting mathematical properties.

Derangement Numbers for Small Values of n

Relationship Between Derangements and Factorials

Derangements are closely related to factorials.

Since:

$D_n\approx\frac{n!}{e}$

their growth rate is similar to factorial growth.

Growth Pattern of Derangements

As $n$ increases:

• Derangement numbers grow rapidly.

• The ratio $\frac{D_n}{n!}$ approaches $\frac{1}{e}$.

Important Mathematical Properties

Some important properties are:

• $D_0=1$

• $D_1=0$

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

• $D_n\approx\frac{n!}{e}$

Derangement Table

Derangement values are often tabulated for quick reference.

Derangement Values from $n=1$ to $n=10$

Comparison with Total Permutations

Derangements form only a portion of all permutations.

Derangement Percentage Analysis

The ratio:

$\frac{D_n}{n!}$

approaches:

$\frac{1}{e}\approx0.3679$

Thus approximately 36.79% of all permutations are derangements.

Quick Reference Table

Students often memorize:

$D_2=1,;D_3=2,;D_4=9,;D_5=44,;D_6=265$

for fast calculations.

Applications of Derangement

Derangements have many practical applications.

Applications in Probability

Used to calculate:

• Matching probabilities.

• Random assignment probabilities.

• Secret Santa outcomes.

Applications in Combinatorics

Used in:

• Restricted permutations.

• Counting problems.

• Inclusion-exclusion applications.

Applications in Cryptography

Derangement concepts help design:

• Secure mappings.

• Encryption techniques.

• Randomized systems.

Applications in Computer Science

Used in:

• Algorithm design.

• Data shuffling.

• Assignment optimization.

Derangement and Probability

Probability provides an interesting interpretation of derangements.

Probability of a Random Derangement

Probability that a random permutation is a derangement:

$P=\frac{D_n}{n!}$

Relationship with Euler's Number $e$

As $n$ becomes large:

$\frac{D_n}{n!}\rightarrow\frac{1}{e}$

This creates a surprising connection between combinatorics and Euler's constant.

Probability Formula for Derangements

For large $n$:

$P\approx\frac{1}{e}$

or approximately:

$0.3679$

Interesting Probability Results

This means that for a large number of objects:

There is roughly a 36.79% chance that a random permutation will be a derangement.

Derangement vs Permutation

Although closely related, derangements and permutations are not the same.

Key Differences

Permutation counts all arrangements.

Derangement counts only arrangements with no fixed points.

Formula Comparison

Permutation:

$P=n!$

Derangement:

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

Practical Interpretation

Permutation asks:

"How many arrangements are possible?"

Derangement asks:

"How many arrangements are possible if nothing stays in its original position?"

Comparison Table

Best Books for Derangement

Derangement is an important topic in permutations, combinations, and combinatorics. The following books provide strong conceptual understanding and practice for derangement problems and advanced counting techniques.

Shortcut Tips and Tricks for Derangement

Derangement questions can often be solved quickly by recognizing common patterns and applying standard formulas instead of listing all arrangements manually.

Important Formula Table

The following formulas are commonly used in derangement, permutation, and combinatorics problems.

Solved Examples Based on Derangement

Example 1: In an examination, 5 students have been allotted their seats according to their roll numbers. Find the number of ways in which none of the students sits in the allotted seat. [JEE Main 2023]

Solution:

This is a derangement problem involving 5 students.

Using the derangement formula:

$D_5=5!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\right)$

$\begin{aligned}
D_5&=120\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}\right)\
&=120\left(\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}\right)\
&=60-20+5-1\
&=44
\end{aligned}$

Hence, the number of ways is 44.

Example 2: The number of ways in which a matching arrangement of order $5\times5$ with one-to-one correspondence can be made such that none of the pairs is correctly matched is:

Solution:

We know that if $n$ objects are arranged such that none occupies its original position, then the number of derangements is:

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

For $n=5$,

$\begin{aligned}
D_5&=5!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\right)\
&=120\left(\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}\right)\
&=60-20+5-1\
&=44
\end{aligned}$

Hence, the answer is 44.

Example 3: In how many ways can 10 letters be placed in 10 addressed envelopes such that exactly 9 letters are in the correct envelopes?

Solution:

Suppose exactly 9 letters are placed in their correct envelopes.

Then only one letter remains.

However, that remaining letter must also go into its correct envelope because all other envelopes have already been occupied correctly.

Therefore, such an arrangement is impossible.

Hence, the required number of ways is 0.

Related Topics to Derangement

Derangement is closely related to permutations, combinations, probability, and counting principles. Exploring these topics helps build a stronger understanding of combinatorial mathematics and advanced counting techniques.