Derangement Numbers Explained: Why !n Hovers Near 1/e

A derangement is a permutation where nothing lands back in its starting spot. Label seats 1 through n, reseat everyone so no one sits in their own seat, and you have built one. The count of these arrangements is written !n and read "subfactorial n." It sits one notch away from the ordinary factorial, but the two numbers tell very different stories: n! counts every shuffle, while !n counts only the shuffles that move every single item.

That small difference turns out to power one of the most quoted surprises in probability. The chance a random shuffle leaves nothing in place is !n / n!, and that fraction snaps to about 36.8 percent almost immediately and stays there no matter how big n gets. This post walks through why, with the exact formula, a worked example you can check by hand, and the practical places the number shows up.

What a Derangement Actually Counts

Take three items: 1, 2, 3. There are 3! = 6 permutations. Most of them leave at least one item fixed. The identity 123 fixes all three. The arrangement 132 fixes the 1. Only two permutations move everything: 231 and 312. So !3 = 2.

The vocabulary you will run into: a fixed point is an element that stays put, and a derangement is a permutation with zero fixed points. Mathematicians also call these counts the de Montmort numbers or rencontres numbers, after the early-1700s gambler who first studied them. In the OEIS they are sequence A000166.

A detail that trips people up: !1 = 0, not 1. With a single item there is simply no way to move it off its own position, so the count of valid rearrangements is zero. Only !0 = 1, by the empty-product convention. If you want to confirm any of these by machine, the derangement calculator prints !n, the matching n!, and the ratio between them side by side.

The Recurrence and the 1/e Formula

There are two ways to compute !n, and they serve different purposes.

The recurrence is the one a computer should use:

!n = (n − 1) × ( !(n−1) + !(n−2) )
!0 = 1,  !1 = 0

It is exact integer arithmetic from start to finish, so the answer is correct to the last digit even when it runs to hundreds of digits. The intuition: the first item can move to any of n − 1 spots, and once it does, the rest either form a smaller derangement or a near-derangement with one forced swap — the two terms in the parentheses.

The closed form is the one that explains the magic number:

!n = n! × ( 1 − 1/1! + 1/2! − 1/3! + ... ± 1/n! )

That alternating sum inside the parentheses is the partial sum of the series for e^(−1). As n grows, the parentheses converge to 1/e ≈ 0.367879. So !n approaches n!/e, and dividing both sides by n! shows that the probability of a derangement, !n / n!, approaches 1/e. The series converges so fast that by n = 7 the probability already rounds to 0.3679. This gives the handy shortcut !n = round(n! / e) for any n ≥ 1 — though if you are computing large values in a spreadsheet, the float drifts off once n passes about 18, which is exactly why the recurrence on exact integers is the safer route.

A Worked Example: !4 = 9

Let me grind through n = 4 by hand, because seeing the nine arrangements makes the gap between !n and n! concrete. We need every permutation of 1234 in which position i never holds value i.

2143   2341   2413
3142   3412   3421
4123   4312   4321

That is nine arrangements, every one of them moving all four items. Out of 4! = 24 total permutations, only these nine are derangements, the other fifteen each pinning at least one item. So !4 = 9 and the probability !4 / 4! = 9 / 24 = 0.375 — already within a hair of 1/e. Check it against the recurrence: !4 = 3 × (!3 + !2) = 3 × (2 + 1) = 9. The first handful of values, worth memorizing, run !0 = 1, !1 = 0, !2 = 1, !3 = 2, !4 = 9, !5 = 44, !6 = 265, !7 = 1854, !8 = 14833.

The Hat-Check Problem and Secret Santa

The historical framing is the hat-check problem: n guests each hand a hat to the attendant, who returns them at random. What is the chance nobody gets their own hat back? That is precisely the derangement probability, !n / n! ≈ 1/e ≈ 0.3679. The counterintuitive part is that the answer barely depends on n. Three guests or three hundred, the odds that not one person gets their own hat sit at roughly 37 percent.

The same arithmetic answers a question a lot of offices ask every December. In a Secret Santa or gift exchange, you want a draw where no person pulls their own name. The fraction of valid full draws among all possible draws is again !n / n!. For a group of eight, that is !8 = 14833 clean draws out of 8! = 40320, about 36.8 percent. The practical upshot for anyone scripting the draw: if your code just reshuffles and retries whenever someone draws themselves, it almost never needs more than three attempts. If you would rather skip the math and just generate the assignment, a dedicated Secret Santa generator produces a valid no-self-draw pairing directly.

Where I Reach for This

I first ran into derangements while debugging a task-rotation script — we randomly reassigned on-call shifts each month and wanted nobody keeping their previous slot. My naive instinct was that a blind reshuffle would rarely satisfy that, so I planned an elaborate constraint solver. Then I computed !n / n! for our team size and saw it was about 0.37: more than a third of random shuffles already worked. The whole solver was unnecessary. A reject-and-retry loop hit a valid assignment in two tries on average, and I deleted forty lines of code. That is the everyday value of knowing this number — it tells you when rejection sampling is cheap enough to skip the clever algorithm entirely.

It also makes a memorable classroom hook. Show a stats class !n / n! for n = 4, 5, 10, and 50 and watch it lock onto 0.3679 after just a few terms; the convergence is far more convincing on screen than as a formula on a slide.

Quick Reference

!n counts permutations with no element in its original position; n! counts all of them.
Exact: !n = (n−1)(!(n−1) + !(n−2)), with !0 = 1, !1 = 0.
Series: !n = n!(1 − 1/1! + 1/2! − ...) which approaches n!/e.
Probability !n / n! approaches 1/e ≈ 0.3679 and gets there by n = 7.
Worked value: !4 = 9, against 4! = 24.

If you need the plain factorial alongside, the factorial calculator handles n! on its own, and the combination and permutation calculator covers the broader counting toolkit when your problem has fixed points allowed. For derangements specifically, type an n into the derangement calculator and read !n as an exact integer — no rounding, no drift, even at n = 200.

Made by Toolora · Updated 2026-06-13