Derangement (Subfactorial) Calculator - Calculate !n for Any Number of Elements

What Is a Derangement?

A derangement (also called a subfactorial) is a permutation of elements where no element appears in its original position. The number of derangements of n elements is written as !n (exclamation mark before n, not after) or D(n). Derangements appear in combinatorics, probability theory, and famous puzzles like the hat-check problem.

Key Formulas

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

$$!n = (n-1)\left(!(n-1) + !(n-2)\right)$$

$$!n =\ \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor \quad (n \ge 1)$$

Base cases: !0 = 1, !1 = 0.

Example: !3

For 3 items {A, B, C} with original positions {1, 2, 3}:

Permutation (B, C, A) — A→2, B→3, C→1 ✓
Permutation (C, A, B) — A→3, B→1, C→2 ✓

These are the only derangements out of 6 total permutations, so !3 = 2.

The Hat-Check Problem

If n guests check their hats and the hats are returned randomly, the probability that no guest gets their own hat equals !n/n!. Remarkably, this converges to 1/e ≈ 36.79% as n grows. Even for n = 5, the probability (44/120 ≈ 36.67%) is already very close.

Applications

Secret Santa: A valid draw where nobody picks themselves is a derangement.
Cryptography: Substitution ciphers where no letter maps to itself use derangements.
Card Shuffling: The probability that no card returns to its original position.

How to Use

Enter a number n (0-170) for the number of elements.
View !n, n!, the derangement probability, and 1/e comparison.
Check the step-by-step explanation for the calculation details.

Also check: Factorial Calculator, Combinations and Permutations Calculator, Probability Calculator.

Frequently Asked Questions

What is a derangement?

A derangement is a permutation where no element stays in its original position. For example, for items {1,2,3}, the permutations (2,3,1) and (3,1,2) are derangements. The number of derangements is denoted !n (subfactorial).

What is the formula for subfactorial !n?

The subfactorial can be computed via inclusion-exclusion: !n = n! × sum((-1)^k/k!) for k=0 to n, or recursively: !n = (n-1)(!(n-1) + !(n-2)). A useful approximation is !n ≈ round(n!/e).

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

The probability approaches 1/e ≈ 0.3679 (about 36.79%) as n increases. This convergence is remarkably fast—even for n = 5, the probability is already 44/120 ≈ 36.67%.

What is the hat-check problem?

The classic probability puzzle: if n people check their hats and hats are randomly returned, the probability that no one gets their own hat is !n/n!. The answer converges to 1/e ≈ 36.79%.

Report

Derangement Subfactorial Calculator