Derangements

Understanding Derangements

Derangements are a fascinating concept in the field of combinatorics, a branch of mathematics concerned with counting, arrangement, and combination of objects. To understand derangements, let's first define what they are.

What is a Derangement?

A derangement is a permutation of a set of objects such that none of the objects appear in their original position. In other words, a derangement is a complete mismatch of objects and positions. This concept is also known as a "hat-check problem," where no guest gets back their own hat.

Derangement Formula

The number of derangements of n distinct objects is denoted by !n, which is also known as the "subfactorial" of n. The formula for calculating derangements is derived from the principle of inclusion-exclusion and can be expressed as:

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

Alternatively, it can be recursively defined as:

$$ !n = (n - 1) \times (!(n - 1) + !(n - 2)) $$

with the initial conditions:

$$ !0 = 1 \quad \text{and} \quad !1 = 0 $$

Table of Differences and Important Points

Aspect	Permutations	Derangements
Definition	Arrangements of objects where each object can be in any position.	Arrangements of objects where no object is in its original position.
Formula	`n!` for `n` objects.	`!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}`
Initial Conditions	N/A	`!0 = 1`, `!1 = 0`
Example for 3 objects	(1, 2, 3), (3, 1, 2), etc.	(2, 3, 1), (3, 1, 2)
Real-world Example	Seating arrangements at a table.	Hat-check problem where no one gets their own hat back.

Examples to Explain Important Points

Example 1: Derangement of 3 Objects

Let's say we have three objects labeled A, B, and C. The permutations of these objects are:

Out of these, the derangements (where no object is in its original position) are:

So, !3 = 2.

Example 2: Calculating Derangements

Let's calculate the number of derangements for 4 objects using the formula:

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

$$ !4 = 24 \left( 1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} \right) $$

$$ !4 = 24 \left( \frac{12}{24} - \frac{4}{24} + \frac{1}{24} \right) $$

$$ !4 = 24 \times \frac{9}{24} $$

$$ !4 = 9 $$

So, there are 9 derangements of 4 distinct objects.

Example 3: Recursive Calculation

Using the recursive formula, let's calculate !5:

$$ !5 = 4 \times (!(4) + !(3)) $$

We already know that !4 = 9 and !3 = 2, so:

$$ !5 = 4 \times (9 + 2) $$

$$ !5 = 4 \times 11 $$

$$ !5 = 44 $$

So, there are 44 derangements of 5 distinct objects.

Understanding derangements is not only a fun intellectual exercise but also has practical applications in fields such as cryptography and probability theory. It's a great example of how seemingly abstract mathematical concepts can have real-world implications.