Derangements: Counting Arrangements With No Fixed Points
How can we count or model shuffles in which nobody receives their own item?
How this lesson unfolds.
Begin with What is a fixed point in a permutation, and what defines a derangement? The sequence then connects Indicator Variables Break Down the Hat Check Problem and builds toward Exactly k Correct Means Derange Everyone Else.
What is a fixed point in a permutation, and what defines a derangement?
Shuffling a deck of cards or returning coats at a party can leave some items in their original slots or scramble every single one. A derangement is a total scramble where not a single person gets their own coat back.
- $$\pi \in S_n, \quad \text{Fixed Point: } \pi(i) = i, \quad \text{Derangement } D_n: \forall i, \; \pi(i) \ne i$$
- $$A permutation $\pi$ maps $\{1, \dots, n\}$ to itself; a fixed point is an element where $\pi(i) = i$.$$
- Learning goalDefine permutations, fixed points, and derangements algebraically and combinatorially.
- Helpful foundationsPermutations and symmetric group Sₙ · One-to-one functions · Fixed-point definitions · Foundations of the Theory of Probability (Andrey Kolmogorov, 1933) · An Essay towards solving a Problem in the Doctrine of Chances (Thomas Bayes, 1763)
- Common trapA derangement is any permutation without fixed points, regardless of cycle structure.
- Next connectionModel the classical 'Hat Check Problem' using random indicator variables.
More context & mechanics
Let n people check their hats at a restaurant. If the hats are returned completely at random, this corresponds to selecting a permutation π ∈ Sₙ uniformly at random from all n! possibilities. If person i receives their own hat, π(i) = i, which is a fixed point. If nobody gets their own hat back (π(i) ≠ i for all i), the permutation is a derangement. The total number of derangements is denoted Dₙ or !n.
In cryptographic protocols and anonymization algorithms (such as oblivious shuffling or Secret Santa assignment algorithms), engineers use derangements to guarantee that no user is ever routed to their own original encryption key or assigned to themselves.
Pierre Rémond de Montmort first posed and solved the derangement problem in 1708 in his book Essay d'analyse sur les jeux de hazard, calling it the game of Treize (Thirteen).
'Nobody Gets Their Own': A derangement is total chaos. If even one person gets their own hat back, it's not a derangement.
How do indicator variables simplify counting how many people receive their own hat?
Tracking the entire hat-check mess at once gives you a headache. Instead, assign an indicator switch to each guest: 1 if they hold their own hat, 0 if it belongs to someone else.
- $$X = \sum_{i=1}^n I_i, \quad I_i = 1 \iff \pi(i) = i$$
- $$Define $I_i = 1$ if person $i$ gets their own hat and $0$ otherwise; the total number of correct hats is simply the sum of indicators $X = \sum_{i=1}^n I_i$.$$
- Learning goalExpress fixed point counts as sums of individual Bernoulli indicator variables.
- Helpful foundationsIndicator random variables · Permutations · Summation notation · Foundations of the Theory of Probability (Andrey Kolmogorov, 1933) · An Essay towards solving a Problem in the Doctrine of Chances (Thomas Bayes, 1763)
- Common trapIndicator variables decompose global permutation counting into n simple individual binary questions.
- Next connectionCompute the probability that any single individual person gets their own hat.
More context & mechanics
Instead of tackling the complicated global question 'How many people get their own hat?', we decompose it into n microscopic binary questions. For each person i, create an indicator switch Iᵢ. If person i gets their own hat, flip the switch to 1; if not, leave it at 0. The total number of people with their correct hats is the sum X = I₁ + I₂ + ṡ + Iₙ. Decomposing global counts into indicators is the master key to discrete probability.
In genome sequence alignment algorithms (e.g. BLAST), bioinformaticians use indicator variables to count conserved gene positions (synteny blocks) between two shuffled bacterial chromosomes.
Leonhard Euler studied fixed points in permutations in 1753, formalizing recurrence relations that bridged combinatorial geometry and algebraic number theory.
'One Switch per Person': Don't count the room all at once. Ask each person: 'Do you have your hat?' (+1 or +0) and add the answers.
Why is the marginal probability of any individual person getting their own hat always exactly 1/n?
Every individual guest looking into the dark cloakroom has an identical 1/n chance of drawing their own hat. The hats do not care who reaches in first; by pure symmetry, each guest probability is 1/n.
- $$P(I_i = 1) = \frac{(n-1)!}{n!} = \frac{1}{n} \implies E[I_i] = \frac{1}{n}$$
- $$By symmetry, all $n$ hats are equally likely to land on person $i$'s head; exactly 1 of those $n$ hats is their own, so $P(I_i = 1) = 1/n$.$$
- Learning goalCalculate individual indicator marginal probabilities using permutation counting and symmetry.
- Helpful foundationsPermutations formula n! · Symmetry in probability · Marginal probability · Foundations of the Theory of Probability (Andrey Kolmogorov, 1933) · An Essay towards solving a Problem in the Doctrine of Chances (Thomas Bayes, 1763)
- Common trapBy permutation symmetry, every position shares the identical marginal match probability 1/n.
- Next connectionSum the expectations across all n people using linearity of expectation.
More context & mechanics
Consider person i. Out of all n! equally likely permutations of n hats, how many assign hat i to person i? If hat i is locked onto person i's head, the remaining n-1 hats can be scrambled among the other n-1 people in (n-1)! ways. Therefore, the probability is ((n-1)!) / (n!) = 1/n. This holds for every single person, whether they are first, middle, or last in line.
In distributed hash tables (DHTs like Chord or Consistent Hashing), data keys are mapped across n servers. Symmetry ensures each server has an identical 1/n marginal probability of hosting a target key.
Thomas Bayes and Abraham de Moivre recognized the principle of symmetry: when no information distinguishes one position from another, their marginal probabilities must be identical.
'One Hat Out of n': There are n hats in the pile. Exactly 1 belongs to you. Your chance is 1/n.
Why is the expected number of people who get their own hat back always exactly 1, whether n=10 or n=1,000,000?
Whether 10 people or 10 million people throw their hats into a pile and pick one at random, the average number of people who get their own hat back is always exactly 1. Linearity adds n copies of 1/n to equal 1.
- $$E[X] = \sum_{i=1}^n E[I_i] = n \cdot \frac{1}{n} = 1 \quad (\forall n \ge 1)$$
- $$By linearity of expectation, $E[X] = \sum_{i=1}^n E[I_i] = \sum_{i=1}^n \frac{1}{n} = n \times \frac{1}{n} = 1$; the population size $n$ completely cancels out!$$
- Learning goalApply linearity of expectation to prove the scale-invariant expectation of permutation fixed points.
- Helpful foundationsLinearity of expectation · Indicator expectation · Derangements setup
- Common trapExpected fixed points remain exactly 1 for any size n by scaling cancellation.
- Next connectionEvaluate pairwise joint probabilities to test indicator independence.
More context & mechanics
This is one of the most astonishing invariance results in probability. Let X = ∑_(i=1)^n Iᵢ. Linearity of expectation allows us to distribute expectation inside the sum unconditionally: E[X] = ∑_(i=1)^n E[Iᵢ]. Since each individual's expectation is E[Iᵢ] = 1/n, we add 1/n exactly n times: n × (1/n) = 1. Whether n=3, n=100, or n=8 billion humans on Earth throwing their smartphones into a pile, the expected number of people who get their own phone back is exactly ONE.
In random graph theory and network routing, when n packets are misrouted to n random nodes, the expected number of packets that accidentally land on their correct destination node is exactly 1.
Pierre Rémond de Montmort discovered this invariance in 1713, noting with awe that expectation remains frozen at unity regardless of the number of cards in the deck.
'n People Times 1/n Chance': n × 1/n = 1. The n's cancel out completely. Always 1!
Are the indicator variables Iᵢ and Iⱼ independent, and how do we compute their joint probability?
If Alice gets her own hat, Bob odds of getting his own hat tick up slightly because Alice is not holding his hat hostage. The indicators are correlated, yet their expectations add cleanly regardless.
- $$P(I_i = 1, I_j = 1) = \frac{1}{n(n-1)} \ne P(I_i=1)P(I_j=1) = \frac{1}{n^2}$$
- $$Indicators are dependent: if person 1 gets hat 1, person 2 only has $n-1$ hats left to choose from; the joint probability is $P(I_1=1, I_2=1) = \frac{1}{n(n-1)} \ne \frac{1}{n^2}$.$$
- Learning goalCalculate joint probabilities of dependent indicator variables and demonstrate failure of independence.
- Helpful foundationsJoint probability · Conditional probability · Dependent events
- Common trapDrawing without replacement creates dependent indicators: one person's outcome alters remaining hat choices.
- Next connectionCompute the variance of total correct hats taking covariance into account.
More context & mechanics
If person i and person j both get their own hats, hats i and j are fixed in place. The remaining n-2 hats can be arranged in (n-2)! ways. The joint probability is ((n-2)!) / (n!) = (1) / (n(n-1)). If they were independent, the joint probability would be 1/n × 1/n = (1) / (n²). Because (1) / (n(n-1)) > (1) / (n²), the indicators are positively correlated: if person i gets their own hat, it slightly increases the chance that person j gets theirs (since person i did not steal person j's hat!).
In distributed consensus protocols (e.g. Raft or Paxos leader election), vote outcomes among nodes are correlated because a vote cast for leader candidate A removes that vote from candidate B.
Abraham de Moivre analyzed this correlation in his 1738 edition of The Doctrine of Chances, establishing that sampling without replacement introduces positive covariance among fixed-point indicators.
'Two Fixed Hats': Lock 2 hats in place; the chance is 1/n for the first, and 1/(n-1) for the second: (1) / (n(n-1)).
How does expanding Var(∑ Iᵢ) reveal that the variance of correct hats is also exactly 1?
Even though the indicators depend on each other, computing the variance of the total number of correct hats reveals another stunning invariance: the variance is also exactly 1, regardless of how large n is.
- $$\text{Var}(X) = n\text{Var}(I_i) + n(n-1)\text{Cov}(I_i, I_j) = 1$$
- $$Expanding $\text{Var}(X) = \sum \text{Var}(I_i) + \sum_{i \ne j} \text{Cov}(I_i, I_j)$ shows that individual variances sum to $1 - 1/n$ and covariances sum to $1/n$, totaling exactly $\text{Var}(X) = 1$.$$
- Learning goalDerive dependent indicator sum variance using marginal variances and pairwise covariances.
- Helpful foundationsVariance of a sum · Covariance formula · Indicator variance
- Common trapDependent indicators require including all n(n-1) pairwise covariance terms when computing variance.
- Next connectionRecognize that mean 1 and variance 1 foreshadow the Poisson distribution.
More context & mechanics
To find Var(X), we use the full expansion: Var(X) = ∑_(i=1)^n Var(Iᵢ) + ∑_(i ≠ j) Cov(Iᵢ, Iⱼ).
- For each indicator: Var(Iᵢ) = E[Iᵢ²] - (E[Iᵢ])² = 1/n - (1) / (n²) = (n-1) / (n²). Summing n terms gives n × (n-1) / (n²) = (n-1) / (n).
- For each pair: Cov(Iᵢ, Iⱼ) = E[Iᵢ Iⱼ] - E[Iᵢ]E[Iⱼ] = (1) / (n(n-1)) - (1) / (n²) = (1) / (n²(n-1)).
There are n(n-1) pairs, so the total covariance is n(n-1) × (1) / (n²(n-1)) = 1/n.
Adding them together: Var(X) = (n-1) / (n) + 1/n = 1.
Both mean and variance equal 1 for all n ≥ 2!
In random permutation tests in statistics (Permutation Feature Importance in Random Forests), knowing that fixed-point counts have mean 1 and variance 1 establishes instant Z-score baselines for null hypothesis testing.
Pafnuty Chebyshev introduced this method of expanding sums of covariances in 1867, unlocking modern moment-based asymptotic proofs.
'Twin Ones': For the hat check problem, Mean = 1 and Variance = 1. The two fundamental moments are both locked at 1.
Why does knowing E[X] = 1 not tell us the probability of zero people getting their hat back?
Knowing the expected value is 1 does not mean you will always get 1 correct hat: sometimes 0 people get their hat, sometimes 3 people do, but never 0.5. You need the full probability mass function to see the whole landscape.
- $$E[X] = 1, \quad P(X = 0) \approx 1/e \approx 0.368$$
- $$Expectation is merely an average balance point; the full probability mass function $P(X = k)$ describes the complete spectrum of possibilities for each $k \in \{0, 1, \dots, n\}$.$$
- Learning goalDistinguish between summary expected values and complete probability mass distributions.
- Helpful foundationsExpected value · Probability mass function · Derangements concept
- Common trapAn expected value of 1 does not make 0 rare; X=0 is actually most probable.
- Next connectionDerive the exact formula for P(X=k) using the derangement count D_(n-k).
More context & mechanics
Knowing that E[X] = 1 is valuable, but it leaves critical operational questions unanswered. What is the chance that zero people get their hat back? What is the chance that everyone gets their hat back? To answer these questions, we must find the full PMF P(X=k) for every possible count k ∈ 0, 1, ṡ, n. In particular, finding P(X=0) requires counting derangements—permutations with zero fixed points.
In cybersecurity risk analysis, the expected number of compromised servers might be E[X] = 1. But the CISO cares about the distribution: P(X=0) (clean network) vs P(X ≥ 5) (catastrophic lateral movement breach).
Pierre Rémond de Montmort struggled for five years to transition from simple averages to the full PMF of derangements, finally publishing the complete recursive solution in 1713.
'Average is Not the Spread': An average depth of 3 feet in a river doesn't prevent you from drowning in a 10-foot hole. You need the whole PMF.
How do we express the probability of exactly k fixed points in terms of derangements D_(n-k)?
To calculate the probability that exactly k people get their own hat, choose which k lucky people they are, and then require the remaining n - k guests to suffer a complete derangement.
- $$P(X = k) = \frac{\binom{n}{k} D_{n-k}}{n!} = \frac{1}{k!} \frac{D_{n-k}}{(n-k)!}$$
- Learning goalFormulate the exact probability mass function for permutation fixed points using combinations and derangements.
- Helpful foundationsCombinations C(n, k) · Derangements Dₙ · Multiplication principle
- Common trapThe remaining n-k elements must be strictly deranged to prevent creating extra fixed points.
- Next connectionCalculate the number of derangements Dₙ using the Principle of Inclusion-Exclusion.
More context & mechanics
To find the probability of exactly k matches:
- Choose which k individuals receive their own hats: C(n, k) ways.
- The remaining n-k individuals must NOT receive their own hats! If any of them did, we would have more than k matches. Thus, the remaining n-k people must form a derangement: D_(n-k) ways.
Multiplying these stages gives the favorable outcomes C(n, k) D_(n-k). Dividing by total permutations n! yields P(X=k) = (C(n, k) D_(n-k)) / (n!) = (1) / (k!) (D_(n-k)) / ((n-k)!).
In software fuzzing test coverage analysis, when randomly shuffling test execution suites, engineers calculate P(X=k) to evaluate the probability that exactly k unit tests execute in their original baseline order.
Nicholas Bernoulli (nephew of Jacob Bernoulli) corresponded with Montmort in 1710, helping formulate this exact factorial quotient decomposition.
'Pick k, Derange the Rest': Choose the k winners (C(n, k)), then strictly forbid any remaining person from winning (D_(n-k)). Divide by n!.
How does the Principle of Inclusion-Exclusion define the 'bad sets' we must eliminate to find derangements?
To find permutations where nobody gets their hat, define the 'bad' set Aᵢ as all arrangements where person i gets their correct hat. We want the permutations that dodge every single bad set.
- $$A_i = \{ \pi \in S_n : \pi(i) = i \}, \quad D_n = n! - \left| \bigcup_{i=1}^n A_i \right|$$
- $$Let $A_i$ be the set of permutations where person $i$ receives their own hat; a derangement is the complement of their union: $D_n = |\bigcap_{i=1}^n A_i^c| = n!$$
- $$- |\bigcup_{i=1}^n A_i|$.$$
- Learning goalDefine bad sets in permutation spaces and set up the Inclusion-Exclusion complement formula.
- Helpful foundationsSet unions and intersections · De Morgan's laws · Permutations
- Common trapSubtracting individual set sizes directly double-counts overlapping permutations where multiple people match.
- Next connectionAnalyze why naive subtraction removes intersecting permutations twice.
More context & mechanics
A derangement is a permutation where no one gets their own hat. It is much easier to define the 'bad' events: let Aᵢ be the set of permutations where person i gets their own hat. Person i is fixed, and the remaining n-1 people can do whatever they want in (n-1)! ways: |Aᵢ| = (n-1)!. We want the permutations in none of the bad sets: cap Aᵢ^c = (cup Aᵢ)^c. The count of derangements is Dₙ = n! - |cup_(i=1)^n Aᵢ|.
In database query optimization and relational algebra, computing anti-joins (A \setminus cup Bᵢ) utilizes identical inclusion-exclusion complement counting to avoid massive Cartesian product blowups.
Abraham de Moivre published the Inclusion-Exclusion Principle in his 1718 book The Doctrine of Chances, providing the first general algorithm for multi-set union cardinalities.
'Subtract the Bad from the Total': Total permutations is n!. Bad permutations have at least one match (cup Aᵢ). Derangements = Total minus Bad.
What combinatorial error occurs if you simply subtract ∑ |Aᵢ| from total permutations n!?
If you simply subtract the size of each bad set from n!, you subtract permutations where both Alice and Bob got their hats twice. Naive subtraction over-penalizes the overlaps.
- $$\pi \in A_1 \cap A_2 \implies \text{counted twice in } \sum |A_i|$$
- Learning goalDemonstrate the over-subtraction error that occurs when subtracting overlapping sets.
- Helpful foundationsVenn diagrams · Set intersections · Principle of Inclusion-Exclusion
- Common trapSet sizes add to union size only when sets are completely disjoint.
- Next connectionAdd back pairwise intersections to repair the double-subtraction.
More context & mechanics
Suppose n=3. We start with total permutations 3! = 6. We subtract |A₁| + |A₂| + |A₃| = 2 + 2 + 2 = 6. The result is 6 - 6 = 0. But wait! Are there really zero derangements? No! The permutations (2, 3, 1) and (3, 1, 2) are valid derangements! Why did our math say 0? Because the identity permutation (1, 2, 3) fixes person 1, person 2, AND person 3. It was subtracted three times! Naive subtraction subtracts overlaps too many times.
In web traffic unique visitor counting (e.g. HyperLogLog algorithms), overlapping user sessions across devices must correct for double-counting to prevent severe underestimation of unique reach.
Daniel Bernoulli highlighted this double-counting fallacy in 1760 while modeling smallpox contagion immunity across overlapping demographic cohorts.
'Over-Subtraction Trap': If Alice and Bob both have their hats, you subtracted Alice's list, and you subtracted Bob's list. You kicked that permutation out twice!
How does adding back pairwise intersections |Aᵢ ∩ Aⱼ| begin repairing the count?
Inclusion-exclusion repairs the over-subtraction: adding back all pair intersections (n - 2)! restores the balance for two fixed hats, just like adding back the intersection in a two-circle Venn diagram.
- $$\sum_{1 \le i < j \le n} |A_i \cap A_j| = \binom{n}{2}(n-2)! = \frac{n!}{2!}$$
- $$For any pair $\{i, j\}$, fixing both people leaves $(n-2)!$ ways to arrange the rest; adding $\sum_{i<j} |A_i \cap A_j| = \binom{n}{2}(n-2)!$ restores the over-subtracted pairs.$$
- Learning goalCalculate the size and number of pairwise set intersections in permutation spaces.
- Helpful foundationsCombinations C(n, 2) · Set intersections · Inclusion-Exclusion steps
- Common trapCount pair intersections with combinations C(n, 2); set intersection order does not distinguish pairs.
- Next connectionExamine what happens to permutations that fix three people simultaneously.
More context & mechanics
To fix the double-subtraction, we add back every pair intersection |Aᵢ ∩ Aⱼ|. How many permutations fix both person i and person j? Exactly (n-2)!, since the remaining n-2 hats can be shuffled freely. How many distinct pairs of people are there? C(n, 2) = (n(n-1)) / (2). Multiplying gives C(n, 2)(n-2)! = (n!) / (2!(n-2)!)(n-2)! = (n!) / (2!). Adding this back brings the running total to: n! - (n!) / (1!) + (n!) / (2!).
In network reliability engineering, calculating the probability that a distributed mesh network remains connected requires adding back pairwise link failure intersections to prevent underestimating network survival.
Leonhard Euler in 1779 published Calcul de la probabilité dans le jeu de rencontre, using these exact alternating factorial terms to calculate lottery ticket match probabilities.
'Add Back the Pairs': Subtracted pairs twice? Add them back once! C(n, 2)(n-2)! = (n!) / (2!).
Why does adding back pair intersections over-compensate for permutations that fix three people?
When three guests get their correct hats, they were subtracted 3 times in singletons and added back 3 times in pairs. They are currently back at +0, so they must be subtracted once more in the triple intersection.
- $$\text{Weight on 3-overlap: } 1 - \binom{3}{1} + \binom{3}{2} - \binom{3}{3} = 0$$
- $$A permutation fixing 3 people is included in $\binom{3}{1}=3$ single sets, added back in $\binom{3}{2}=3$ pair sets, netting $1 - 3 + 3 = +1$; it must be subtracted again via triple intersections.$$
- Learning goalExplain the algebraic necessity of alternating signs in the Inclusion-Exclusion formula.
- Helpful foundationsBinomial coefficients · Alternating sums · Inclusion-Exclusion mechanics
- Common trapHigher-order overlaps require alternating signs to correct cascading waves of over-counting.
- Next connectionGeneralize this alternating bookkeeping to intersections of all sizes.
More context & mechanics
Track a permutation π that fixes exactly 3 people (say persons 1, 2, and 3):
- Counted in total n!: +1
- Subtracted in single sets A₁, A₂, A₃: -3
- Added back in pair sets (A₁ ∩ A₂), (A₁ ∩ A₃), (A₂ ∩ A₃): +3
Net count so far: 1 - 3 + 3 = +1. But this permutation is NOT a derangement! It has 3 fixed points! Its net weight should be 0! To cancel this +1, we must subtract the triple intersection |A₁ ∩ A₂ ∩ A₃|: C(n, 3)(n-3)! = (n!) / (3!). The alternating pendulum swings again.
In database join-size estimation (System R optimizer), query plan compilers use inclusion-exclusion bounds (Bonferroni inequalities) truncated at order 3 to estimate SQL filter selectivity.
Joseph-Louis Lagrange in 1776 formulated the general polynomial expansion of indicator intersections, proving that the binomial identity ∑_(k=0)^m (-1)^k C(m, k) = 0 governs inclusion-exclusion.
'The Combinatorial Pendulum': Subtracted too much? Add. Added too much? Subtract. The pendulum swings -, +, -, + until every non-derangement hits 0.
How does the binomial identity ∑_(k=0)^m (-1)^k C(m, k) = (1-1)^m = 0 guarantee perfect cancellation for all non-derangements?
The alternating signs (+, -, +, -) in inclusion-exclusion act like a pendulum settling onto the exact truth: each level corrects the over-adjustment of the previous tier until all overlaps are counted exactly once.
- $$\sum_{k=0}^m (-1)^k \binom{m}{k} = (1 - 1)^m = 0 \quad (m \ge 1)$$
- $$Any permutation with $m \ge 1$ fixed points is counted with net weight $\sum_{k=0}^m (-1)^k \binom{m}{k} = (1-1)^m = 0$; only derangements ($m=0$) survive with net weight $(-1)^0 \binom{0}{0} = 1$.$$
- Learning goalValidate the Principle of Inclusion-Exclusion using the binomial expansion (1-1)^m.
- Helpful foundationsBinomial theorem · Combinatorial identities · Inclusion-Exclusion proof
- Common trapInclusion-Exclusion is an exact algebraic identity, annihilating every non-derangement completely.
- Next connectionAssemble the complete derangement formula and evaluate it for n=6.
More context & mechanics
Consider ANY permutation with exactly m fixed points. How many times is it counted in the alternating sum n! - ∑ |Aᵢ| + ∑ |Aᵢ ∩ Aⱼ| - ṡ? In an intersection of k sets, it is counted once for every way to choose k of its m fixed points: C(m, k) times. Its net count is: C(m, 0) - C(m, 1) + C(m, 2) - ṡ + (-1)^m C(m, m) = (1 - 1)^m. If m ≥ 1, (1-1)^m = 0^m = 0. It is completely eliminated! If m = 0 (a derangement), it is counted (1-1)⁰ = 1 time. Only derangements survive!
In hardware logic circuit minimization (Karnaugh maps and Quine-McCluskey algorithm), Boolean terms are simplified by canceling overlapping minterms using this exact alternating identity.
Sylvester in 1883 called this principle the Sieve Method, formalizing how alternating signs act as a mathematical sieve letting only coprime or unconstrained elements pass through.
'(1-1)^m = 0': If you have even ONE fixed point (m ≥ 1), the alternating binomial sum flattens you to 0. Only m=0 survives as 1.
What is the closed-form formula for Dₙ, and why does the probability of a derangement rapidly converge to 1/e?
Dividing the derangement count Dₙ by total permutations n! reveals the power series for e^(−1): as party size n grows, the probability that nobody gets their own hat converges rapidly to 1/e, approximately 36.8%.
- $$D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \implies \lim_{n \to \infty} \frac{D_n}{n!} = \frac{1}{e}$$
- $$Factoring $n!$ yields $D_n = n!$$
- $$\sum_{k=0}^n \frac{(-1)^k}{k!}$; as $n \to \infty$, the alternating series equals the Taylor series of $e^{-1}$, so $P(\text{Derangement}) \to 1/e \approx 36.79\%$.$$
- Learning goalCalculate derangement numbers Dₙ and prove their asymptotic convergence to n!/e.
- Helpful foundationsTaylor series for e^x · Factorial algebra · Asymptotic limits
- Common trapDerangement probability does not vanish as n → ∞; it converges rapidly to 1/e ≈ 36.8\%.
- Next connectionAssemble the complete fixed-point probability mass function for general k.
More context & mechanics
Factoring n! out of each term in our alternating expansion reveals an incredible pattern:
Dₙ = n! - (n!) / (1!) + (n!) / (2!) - (n!) / (3!) + ṡ + (-1)^n (n!) / (n!) = n! ∑_(k=0)^n ((-1)^k) / (k!).
For n=6: D₆ = 720 (1 - 1 + 1/2 - 1/6 + 1/24 - 1/120 + 1/720) = 265. The probability of a derangement is 265/720 ≈ 0.36805. The infinite series ∑_(k=0)^∞ ((-1)^k) / (k!) is the exact Taylor expansion of e^x evaluated at x = -1, which is e^(−1) = 1/e ≈ 0.367879. By n=4, the probability is already within 0.005 of 1/e!
In cryptographic randomized key permutations (like AES S-Box generation and RC4 key scheduling), algorithms verify that key permutations do not have fixed points, matching the theoretical 1/e rejection sampling efficiency.
Leonhard Euler connected derangements to the transcendental constant e in 1753, bridging discrete combinatorics and continuous analysis for the first time in history.
'n! Times the 1/e Series': Dₙ = n! ((1) / (0!) - (1) / (1!) + (1) / (2!) - ṡ). Round n!/e to the nearest integer, and you have Dₙ!
Why is it mathematically impossible to have exactly n-1 fixed points in a permutation?
You can never have a party where exactly n - 1 people get their own hats: if n - 1 people are holding their own hats, the last person is holding the only hat left, which must be their own.
- $$P(X = k) \xrightarrow{n \to \infty} \frac{e^{-1}}{k!}, \quad P(X = n-1) = 0$$
- $$If $n-1$ people receive their correct hats, the 1 remaining hat must belong to the 1 remaining person, forcing $n$ fixed points; thus $P(X = n-1) = 0$ while $P(X=k) \approx \frac{e^{-1}}{k!}$.$$
- Learning goalProve fixed-point PMF convergence to the Poisson distribution with parameter λ=1.
- Helpful foundationsDerangements PMF · Poisson distribution · Combinatorial constraints
- Common trapA permutation cannot fix exactly n-1 elements: the remaining element must also match, so P(X=n-1)=0.
- Next connectionConnect permutation fixed points to Poisson approximations for dependent indicator sums.
More context & mechanics
We can now write down the full distribution of fixed points X for large n:
P(X=k) = (1) / (k!) (D_(n-k)) / ((n-k)!) ≈ (1) / (k!) (1/e) = (e^(−1) 1^k) / (k!).
This is PRECISELY the formula for a Poisson(λ = 1) random variable! The number of people getting their own hat back follows a Poisson distribution with mean λ = 1. Notice the curious hole in the distribution: P(X = n-1) = 0. If n-1 people have their hats, the last hat must be the final person's hat (X=n). You can have 0, 1, 2, ..., n-2, or n fixed points, but NEVER n-1.
In distributed database partition reconciliation (e.g. DynamoDB anti-entropy), vector clock exchange discrepancies between n nodes follow this Poisson distribution, enabling bounded gossip-sync protocol design.
Siméon Denis Poisson formulated the Poisson limit law in 1837; early 20th-century probabilists recognized that derangements provide the purest combinatorial example of Poisson convergence.
'The Poisson(1) Curve with a Missing Tooth': Hat matches follow (1) / (e · k!). k=0 is 36.8\%, k=1 is 36.8\%, k=2 is 18.4\%, and k=n-1 is strictly ZERO.