Derangement (Subfactorial) Calculator

Welcome to the Derangement (Subfactorial) Calculator, a comprehensive combinatorics tool that calculates the number of derangements for any set of n elements. A derangement is a permutation where no element appears in its original position, denoted !n or D(n). Whether you are studying combinatorics, solving the classic hat-check problem, or exploring probability theory, this calculator provides detailed step-by-step solutions with interactive visualizations.

What is a Derangement?

A derangement (also called a subfactorial) is a permutation of elements of a set where no element appears in its original position. The number of derangements of n elements is written as !n (with the exclamation mark before n) or D(n).

For example, consider three items in positions {1, 2, 3}. There are 3! = 6 total permutations, but only 2 are derangements:

• (2, 3, 1) — item 1 goes to position 2, item 2 goes to position 3, item 3 goes to position 1
• (3, 1, 2) — item 1 goes to position 3, item 2 goes to position 1, item 3 goes to position 2

So !3 = 2.

Derangement Formulas

Inclusion-Exclusion Formula

The most fundamental formula derives from the inclusion-exclusion principle:

Recursive Formula

Derangements can also be computed recursively:

with base cases: !0 = 1, !1 = 0.

Nearest Integer Formula

For \(n \geq 1\), the subfactorial equals the nearest integer to \(n!/e\):

The Hat-Check Problem

The most famous application of derangements is the hat-check problem (problème des rencontres): if n guests check their hats and the hats are returned randomly, what is the probability that no guest gets their own hat?

The answer is \(!n / n!\), which converges remarkably quickly to \(1/e \approx 0.3679\). This means roughly 36.8% of all random permutations are derangements, regardless of how many items there are.

How to Use This Calculator

1. Enter n: Input the number of elements (0 to 170). Use the quick example buttons to try common values.
2. Calculate: Click "Calculate !n" to compute the derangement number.
3. Review results: See !n, n!, the derangement probability, and the ratio to 1/e.
4. Explore the animation: For small n, interact with the visual animation to see how derangements work.
5. Study the steps: Examine the detailed inclusion-exclusion breakdown and derangement table.

First 15 Derangement Numbers

Applications of Derangements

Secret Santa / Gift Exchange

When organizing a Secret Santa gift exchange, each participant draws a name. A successful draw where nobody picks their own name is a derangement. For a group of 10 people, there are 1,334,961 valid arrangements out of 3,628,800 total.

Cryptography and Coding Theory

Derangements appear in the analysis of substitution ciphers and error-correcting codes. The concept of "no fixed point" is fundamental to understanding cipher strength and permutation-based encryption.

Card Shuffling and Games

In card games, derangements measure the probability that no card returns to its original position after shuffling. This is useful in analyzing shuffle quality and game fairness.

Probability Theory

Derangements provide an elegant example of the inclusion-exclusion principle and illustrate how probabilities can converge to simple limits (1/e in this case).

Key Properties

• The ratio \(!n/n!\) converges to \(1/e \approx 0.367879\) as \(n \to \infty\)
• The convergence is extremely fast — already accurate to 6 decimal places by n = 10
• \(!n\) satisfies the recurrence: \(!n = n \cdot !(n-1) + (-1)^n\)
• The exponential generating function is \(e^{-x}/(1-x)\)
• \(!0 = 1\) (the empty permutation is vacuously a derangement)

Frequently Asked Questions

What is a derangement?

A derangement is a permutation of a set where no element appears in its original position. For example, if items are labeled {1, 2, 3}, the permutation (2, 3, 1) is a derangement because no item is in its original place. The number of derangements of n items is denoted !n (subfactorial n).

What is the formula for subfactorial !n?

The subfactorial !n can be calculated using the inclusion-exclusion formula: \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\). It can also be computed recursively: \(!n = (n-1)(!(n-1) + !(n-2))\), with !0 = 1 and !1 = 0. Another useful formula is \(!n = \text{round}(n! / e)\) for \(n \geq 1\).

What is the probability that a random permutation is a derangement?

The probability that a random permutation of n items is a derangement approaches \(1/e \approx 0.3679\) as n increases. Even for small n, this approximation is remarkably accurate. For n = 5, the exact probability is 44/120 ≈ 0.3667, already very close to 1/e.

What is the hat-check problem?

The hat-check problem (also known as the problème des rencontres) is a classic probability puzzle: if n people check their hats at a restaurant and the hats are randomly returned, what is the probability that no one gets their own hat back? The answer is the number of derangements !n divided by the total permutations n!, which approaches \(1/e \approx 36.79\%\).

What is the relationship between derangements and factorial?

Derangements (!n) and factorials (n!) are closely related: \(!n = n! \times \sum(-1)^k/k!\) for k from 0 to n. The ratio !n/n! gives the probability of a derangement, converging to 1/e. Also, !n is the nearest integer to n!/e for \(n \geq 1\), making n!/e a very useful approximation.

Additional Resources

• Derangement - Wikipedia
• Inclusion-Exclusion Principle - Wikipedia
• OEIS A000166 - Subfactorial Sequence