Derangement & Subfactorial Calculator

Compute !n = D(n) — permutations with no fixed points — with probability, step-by-step recurrence & table

D(n) = !n = (n−1) × [D(n−1) + D(n−2)] D(0)=1, D(1)=0
P(derangement) = D(n) / n! → 1/e ≈ 0.367879...

n — number of elements (0 to 170)

Sample Problems

What is a Derangement?

A derangement is a permutation of a set of elements in which no element appears in its original position — every single element is displaced. In other words, if you number the positions 1 through n and begin with elements arranged in order, a derangement is any rearrangement where element i does not occupy position i for any i.

A simple example: suppose 3 letters labeled A, B, C are in positions 1, 2, 3. The arrangement (B, C, A) is a derangement because A is now in position 3, B in position 1, and C in position 2 — none are home. The arrangement (B, A, C) is NOT a derangement because C is still in position 3.

For n = 3, there are exactly 2 derangements: (B, C, A) and (C, A, B). These are all the permutations of 3 elements that avoid every fixed point.

The Subfactorial (!n) Explained

The number of derangements of n elements is denoted D(n) or written using the subfactorial notation !n (read "subfactorial n"). The exclamation mark comes before the number, contrasting with the usual factorial n! where it follows.

The first eleven subfactorial values are:

n	!n = D(n)	n!	Probability D(n)/n!
0	1	1	1.000000
1	0	1	0.000000
2	1	2	0.500000
3	2	6	0.333333
4	9	24	0.375000
5	44	120	0.366667
6	265	720	0.368056
7	1,854	5,040	0.367857
8	14,833	40,320	0.367882
9	133,496	362,880	0.367879
10	1,334,961	3,628,800	0.367879

Derangement Formula: Two Approaches

1. Inclusion-Exclusion Formula

Using the principle of inclusion-exclusion, we subtract the permutations where at least one element is fixed, add back those where at least two are fixed, and so on:

D(n) = n! × [1 − 1/1! + 1/2! − 1/3! + 1/4! − … + (−1)ⁿ/n!]

D(n) = n! × Σₖ₌₀ⁿ (−1)ᵏ / k!

For example, D(4) = 4! × (1 − 1 + 1/2 − 1/6 + 1/24) = 24 × (3/8) = 9.

2. Recurrence Relation

The most efficient formula for computation uses a two-term recurrence:

D(n) = (n−1) × [D(n−1) + D(n−2)] for n ≥ 2

Base cases: D(0) = 1, D(1) = 0

The recurrence has an elegant combinatorial meaning: when placing element 1, there are (n−1) choices. Say element 1 goes to position j. Then either element j goes to position 1 (n−2 elements remain, giving D(n−2) ways) or element j does not go to position 1 (effectively reducing to D(n−1) ways for the remaining n−1 elements).

3. Nearest Integer Formula (for n ≥ 1)

D(n) = round(n! / e)

Because the series 1/e = 1 − 1 + 1/2! − 1/3! + … converges very fast, D(n)/n! is within 1/(2(n+1)!) of 1/e. For n ≥ 1 this means D(n) is exactly the nearest integer to n!/e.

The Hat-Check Problem

The hat-check problem is the most famous application of derangements. The scenario: n guests arrive at a party and check their hats. A forgetful attendant returns the hats in a completely random order. What is the probability that no guest receives their own hat?

The answer is exactly the derangement probability:

P(no one gets own hat) = D(n) / n!

For n = 4 guests: D(4) = 9 derangements out of 4! = 24 total arrangements. Probability = 9/24 = 0.375 = 37.5%.

What is remarkable is that this probability converges to 1/e ≈ 36.79% extremely quickly. For n = 10 the probability is already 0.367879... — indistinguishable from the limit to 6 decimal places. No matter how large the party, there is always about a 37% chance that the chaos is total and nobody gets their own hat.

Why Does Derangement Probability Approach 1/e?

The probability P(n) = D(n)/n! equals the partial sum of the Taylor series for e^(−1):

P(n) = Σₖ₌₀ⁿ (−1)ᵏ / k! = 1 − 1 + 1/2! − 1/3! + … + (−1)ⁿ/n!

The full series 1/e = e^(−1) = Σₖ₌₀^∞ (−1)ᵏ/k! converges absolutely. The partial sums alternate above and below 1/e, getting exponentially closer with each term. By the alternating series estimation, the error after n terms is less than 1/(n+1)!. For n = 5 this is already less than 1/720 ≈ 0.0014, and for n = 10 less than 1/39916800 — essentially machine precision.

Real-World Applications

Secret Santa: In a group of n people each buying a gift for exactly one other person with no self-gifting, the number of valid assignment arrangements is D(n). For 10 people there are D(10) = 1,334,961 valid exchanges out of 10! = 3,628,800 total assignments.
Card games: The "problème des ménages" asks how many ways n married couples can sit at a round table so that no husband sits next to his wife. A related derangement-like problem appears in many card matching games.
Envelope stuffing problem: If 3 letters are stuffed into 3 envelopes at random, D(3) = 2 gives the number of ways all letters end up in the wrong envelope. The probability is D(3)/3! = 2/6 = 1/3 ≈ 33.3%.
Scheduling & assignment: In scheduling problems where each task must be assigned to a different worker than its current assignment, the number of valid reassignments equals D(n).
Cryptography: Derangements appear in the analysis of certain cipher constructions, particularly those involving substitution permutations where a value should never map to itself.
Biology: In genetics, the analysis of chromosomal rearrangements where no gene remains in its original locus involves derangement-style counting.

Frequently Asked Questions

What is a derangement?

A derangement is a permutation of a set where no element appears in its original position — every element is displaced. For example, with 3 elements {1,2,3} in positions {1,2,3}, the arrangement (2,3,1) is a derangement because 1 is in position 2, 2 is in position 3, and 3 is in position 1 — none are in their starting position. D(3) = 2: the only derangements are (2,3,1) and (3,1,2).

What is the subfactorial !n?

The subfactorial !n is the notation for D(n), the number of derangements of n elements. The exclamation mark is placed before the number. The first few values: !0=1, !1=0, !2=1, !3=2, !4=9, !5=44, !6=265, !7=1854, !8=14833, !9=133496, !10=1334961. The values grow approximately as n!/e.

What is the formula for D(n)?

There are two main formulas. The inclusion-exclusion formula: D(n) = n! × (1 − 1/1! + 1/2! − 1/3! + … ± 1/n!). The recurrence: D(n) = (n−1) × [D(n−1) + D(n−2)] with D(0)=1, D(1)=0. For n ≥ 1, D(n) also equals round(n!/e). All three methods give identical results.

What is the probability of a random derangement?

The probability is P(n) = D(n)/n!, which converges rapidly to 1/e ≈ 0.367879 ≈ 36.79%. By n=10 the probability is 0.367879... — indistinguishable from 1/e to 6 decimal places. This means for any sufficiently large shuffle, about 37% of random permutations are derangements.

What is the hat-check problem?

n people check their hats at a restaurant; the attendant returns them randomly. What is the probability no one gets their own hat? The answer is D(n)/n!. For n=4: D(4)=9 derangements out of 24 arrangements, probability = 9/24 = 37.5%. As n grows, this converges to 1/e ≈ 36.79%, so the chance of total chaos is always roughly 37%.

What is the Secret Santa derangement connection?

Secret Santa requires each of n people to buy for exactly one other person (not themselves). This is a derangement: a permutation where no person maps to themselves. For n=5 people, D(5)=44 valid assignments out of 5!=120 possible, giving probability 44/120 ≈ 36.67%. For n=10, D(10)=1,334,961 valid Secret Santa arrangements exist.

What is D(0) and why is it 1?

D(0) = 1 because the empty permutation (of zero elements) vacuously satisfies "no element is in its original position" — there are no elements to violate the rule. There is exactly one permutation of zero elements, so D(0)=1. D(1)=0 because the only permutation of one element keeps it in place, meaning no derangement of a single element exists.