Derangement Calculator
Calculate D(n) - the number of permutations where no element appears in its original position
Enter a non-negative integer (max 170)
What is a Derangement?
A derangement is a permutation of elements where no element appears in its original position. The number of derangements of n elements is denoted D(n), also written as !n (subfactorial).
Example: For the set {1, 2, 3}, the derangements are {2, 3, 1} and {3, 1, 2}. So D(3) = 2.
Recurrence Formula
Derangements can be calculated using the recurrence relation:
D(n) = (n - 1) × (D(n-1) + D(n-2))
Base cases: D(0) = 1, D(1) = 0
Closed-Form Formula
Using the inclusion-exclusion principle:
D(n) = n! × (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)
This is approximately n!/e, rounded to the nearest integer.
First Few Values
- D(0) = 1 (empty permutation is a derangement)
- D(1) = 0 (single element must stay in place)
- D(2) = 1 (swap the two elements)
- D(3) = 2
- D(4) = 9
- D(5) = 44
- D(10) = 1,334,961
Applications: Secret Santa assignments, hat-check problems, probability theory (probability of no fixed points), and cryptographic shuffling algorithms.
What is a derangement?
A derangement is a permutation where no element appears in its original position. For example, if you have {1, 2, 3}, the arrangements {2, 3, 1} and {3, 1, 2} are derangements because no number is in its starting position, but {1, 3, 2} is not because 1 stays in position 1.
What is the hat-check problem?
The classic hat-check problem asks: if n people check their hats and the hats are returned randomly, what's the probability no one gets their own hat back? As n grows large, this probability approaches 1/e (approximately 0.368). This is the ratio of derangements to all permutations.
What is the formula for counting derangements?
The subfactorial !n equals n! * sum from k=0 to n of (-1)^k/k!. There's also a recurrence: !n = (n-1) * (!(n-1) + !(n-2)). For large n, !n is approximately n!/e rounded to the nearest integer.
Where are derangements used in practice?
Derangements appear in probability theory, secret Santa assignments, card shuffling analysis, and cryptography. They're used to analyze scenarios where complete mixing is required, such as ensuring no person reviews their own work in peer review systems.