What a Derangement Calculator Counts, and Why the Answer Settles at 36.8%
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
Every Secret Santa draw is a gamble, and a derangement calculator is what prices it. Eight names in a hat, everyone pulls one, and the chance that nobody pulls their own name is 36.79%. Add two more people: 36.79%. Add ninety more: still 36.79%. The count itself explodes — !8 = 14,833 while !100 runs to 158 digits — but the odds flatten out almost immediately and then refuse to budge.
That flat line is the interesting part of this problem, and it has a name attached to it: 1/e. Below you’ll find where the constant comes from, the six-number cancellation that turns 120 into 44, the one-step formula that breaks in exactly two places, what happens when you want some people to get their own name, and why a Secret Santa with couples in it is not a derangement problem at all.
The Probability Stops Moving After n = 4
A derangement is a permutation with no fixed points: nothing lands on its own index. The count is written !n and called the subfactorial. What surprises people is not how fast !n grows — it’s that !n/n! converges so violently.
| n | !n | n! | !n / n! | Gap from 1/e |
|---|---|---|---|---|
| 3 | 2 | 6 | 0.333333 | −0.034546 |
| 4 | 9 | 24 | 0.375000 | +0.007121 |
| 6 | 265 | 720 | 0.368056 | +0.000176 |
| 8 | 14,833 | 40,320 | 0.367882 | +0.0000025 |
| 10 | 1,334,961 | 3,628,800 | 0.3678794643 | +2.3 × 10⁻⁸ |
By n = 8 the answer is right to five decimal places. By n = 10 it’s right to seven. The error is bounded by 1/(n+1)!, which collapses faster than anything you’ll meet in a first-year probability course — and it alternates, so consecutive values of n bracket 1/e from above and below. Practically: for any group of five or more, the answer to “what are the odds nobody gets their own?” is 36.8%, and the group size is irrelevant.
There’s a nice consequence worth carrying around. Since the success rate is 1/e, drawing random permutations and restarting whenever somebody matches takes about e ≈ 2.72 attempts on average. Not 10, not 100 — under three tries, whether the group is eight people or eight hundred.
Six Numbers That Turn 120 Into 44
The derivation is inclusion–exclusion, and for n = 5 it fits on one line. Start with all 120 permutations of five items. Subtract the ones that fix at least one item. You’ve now subtracted too much, because a permutation fixing two items got removed twice, so add those back. Keep alternating:
!5 = 120 − 120 + 60 − 20 + 5 − 1 = 44
Each term is 5!/j!, the number of ways to nail down j specific items and let the rest fall anywhere: 120/1, 120/1, 120/2, 120/6, 120/24, 120/120. The general statement is
!n = n! · (1 − 1/1! + 1/2! − 1/3! + … ± 1/n!)
and the bracket is the truncated series for e⁻¹. That’s the whole reason 1/e shows up in a problem about hats. The subtraction of the j = 0 and j = 1 terms cancelling to zero is not a coincidence either — it says that permutations fixing at least one item are, to first order, as numerous as all permutations, and everything interesting lives in the correction terms.
The One-Step Formula, and Why a Derangement Calculator Can’t Rely on It
Because the series converges so fast, !n is simply the nearest integer to n!/e. That collapses the whole computation into one division — and it fails in two specific spots that trip people up.
| Method | Formula | Cost | Where it fails |
|---|---|---|---|
| Nearest integer | round(n!/e) | One division | n = 0 (gives 0, answer is 1); floating point past n ≈ 18 |
| Inclusion–exclusion | Σ (−1)ʲ n!/j! | n + 1 terms | Never — but it’s the slowest route |
| Two-term recurrence | (n−1)(!(n−1) + !(n−2)) | n additions, n multiplications | Never — exact, integers only |
| One-term recurrence | n · !(n−1) + (−1)ⁿ | One multiply per step | Needs the previous value in hand |
The n = 0 failure is small but real: 0! / e = 0.3679, which rounds to 0, while !0 = 1 by convention — the empty arrangement vacuously deranges nothing. The floating-point failure is the one that bites in code. 18! = 6,402,373,705,728,000 is still exactly representable in a double, but 19! isn’t, so round(n!/e) starts returning wrong integers somewhere around there. This calculator uses the two-term recurrence in arbitrary-precision integers instead, which is why it can hand you !250 with all 493 digits intact.
For hand work, the one-term version is unbeatable: !6 = 6 × 44 + 1 = 265, !7 = 7 × 265 − 1 = 1,854, !8 = 8 × 1,854 + 1 = 14,833. Multiply, then add one if n is even and subtract one if n’s odd. Three seconds per step, no series required.
When Exactly k People Get Their Own Hat
“Nobody matches” is one question. “Exactly two people match” is a different one, and it’s the version that shows up on exams. Choose which k items stay put — that’s a combination, C(n,k) — then derange the remaining n − k so none of those match by accident:
D(n, k) = C(n, k) · !(n − k)
These are the rencontres numbers. For five people the full breakdown is:
| Matches k | C(5,k) · !(5−k) | Count | Share of 120 |
|---|---|---|---|
| 0 | 1 × 44 | 44 | 36.67% |
| 1 | 5 × 9 | 45 | 37.50% |
| 2 | 10 × 2 | 20 | 16.67% |
| 3 | 10 × 1 | 10 | 8.33% |
| 4 | 5 × 0 | 0 | 0% |
| 5 | 1 × 1 | 1 | 0.83% |
Three things fall out of that table. The zero at k = 4 is structural: if four of five items are in their own places, the fifth has nowhere to go but its own place, so D(n, n−1) = 0 for every n. The near-tie at the top is structural too — D(n,0) − D(n,1) = (−1)ⁿ, meaning “nobody matches” and “exactly one matches” differ by a single permutation, forever. And the whole column sums to 120, as it must.
The expected number of matches is exactly 1, for every n from 1 upward. Each person has a 1/n chance of drawing themselves, there are n people, and linearity of expectation doesn’t care that the draws are dependent. The variance is 1 as well, once n ≥ 2. Those two facts are the fingerprint of a Poisson(1) distribution, which is precisely what D(n,k)/n! converges to: e⁻¹/k!. That’s the faint marker drawn on each bar in the calculator above.
Secret Santa Stops Being a Derangement the Moment Couples Are Involved
Here’s where the textbook model and the office party part ways. A plain derangement forbids exactly one assignment per person: their own name. Real draws forbid more — spouses shouldn’t draw each other, people who paired up last year shouldn’t repeat, the two contractors shouldn’t be matched. Each extra rule knocks out more cells, and the count is no longer !n; it’s the permanent of a 0-1 matrix, which is a genuinely harder object.
Two shortcuts get used in practice, and only one of them is fair:
- Draw everything, restart if anyone matches. This is uniform over derangements — every valid outcome equally likely — and costs about 2.72 rounds on average. Fair, and cheap.
- Arrange everyone in a random circle, each gives to the next. Fast, always valid, and biased. It only ever produces single-cycle permutations, of which there are (n−1)! = 24 for five people, out of 44 derangements. The 20 outcomes that split into two swaps — like A↔B and C→D→E→C — can never happen. If your group is small enough to notice patterns year over year, they will.
There’s also the version people improvise on the spot: draw one at a time, and if you pull your own name, put it back and draw again. That one can deadlock, because the last person may be left holding an envelope with their own name and nothing to swap it with. It’s not just biased — roughly speaking, it fails outright often enough that someone always has to call a restart.
Three Places the Subfactorial Gets Misused
!n and n! are not the same symbol read from different sides. The exclamation mark leads for a subfactorial and trails for a factorial, and the values diverge fast: 5! = 120 against !5 = 44. Some textbooks write Dn or D(n) to avoid the ambiguity entirely. If you see “!n” in a programming context, check whether it’s actually logical negation before you assume it’s combinatorics.
“At least one match” is the complement, not a separate count. The probability that somebody gets their own item is 1 − !n/n! ≈ 63.2%, and it needs no new formula. People routinely try to compute it directly as n × (n−1)!/n! = 1, which is wrong because it double-counts every permutation with two or more matches — the exact error that inclusion–exclusion exists to fix.
A derangement is not any permutation with restrictions. Derangements forbid one cell per row — the diagonal. Problems like “no student sits in the same seat oran adjacent one” forbid a different pattern and need rook polynomials or a permanent, not !n. If you can’t state the restriction as “item i may not go to position i,” the subfactorial is the wrong tool, and the general combinatorics calculator is a better starting point.
For the raw sequence and its many identities, the OEIS entry A000166 catalogues them exhaustively, and the Wikipedia article on derangements works through the asymptotics in more detail than there’s room for here.
