Questions: Derangements and Fixed-Point-Free Permutations

Question 1

A group of 30 people each write their name on a slip, put it in a bowl, and everyone draws one at random. Approximately what is the probability that nobody draws their own name?

• A. Exactly 1/2, since each person either draws their own name or they don't
• B. Approximately 1/e ≈ 0.368, regardless of the size of the group
• C. Close to 0, since it becomes increasingly unlikely that no one draws their own name as the group grows
• D. Exactly 1/30, because only one permutation has everyone mismatched

Answer: (B)

D(n)/n! = Σ (−1)^k/k! for k=0 to n, which converges to e⁻¹ ≈ 0.368 as n grows. The remarkable fact is that this fraction stabilizes quickly — for groups as small as 5 or 6, the probability is already very close to 1/e. It is not 1/2 (a common guess), and it does not approach 0 as the group grows. Roughly 37% of all permutations are derangements regardless of n.

Question 2

In the inclusion-exclusion derivation of D(n), what do the sets A_i represent, and what are we computing the complement of?

• A. A_i is the set of permutations where element i is NOT in its original position; we count permutations with at least one fixed point
• B. A_i is the set of permutations where element i IS in its original position; we count permutations where none of the A_i events occur
• C. A_i is the set of all derangements of i elements; we sum over all subset sizes
• D. A_i is the set of permutations where elements 1 through i are all fixed; we count permutations with no such prefix

Answer: (B)

A_i is the set of permutations where element i lands in its own original position (a 'fixed point'). We want permutations where NONE of the A_i events occur — no element is fixed. Inclusion-exclusion gives |A_1 ∪ ... ∪ A_n|, and we subtract this from n! to get D(n). The formula D(n) = n! · Σ (−1)^k/k! for k=0 to n emerges from this alternating sum, and its convergence to n!/e is the connection to Euler's number.

Question 3

For large n, the probability that a randomly chosen permutation of n objects is a derangement approaches 1/e ≈ 0.368, regardless of the value of n.

• T. True
• F. False

Answer: True

D(n)/n! = Σ (−1)^k/k! for k=0 to n, which is the partial sum of the Taylor series for e⁻¹. As n → ∞ this converges to e⁻¹ ≈ 0.368. Even for small n (n = 5 or 6), the probability is already very close to 1/e. The fraction of permutations that are derangements stabilizes at about 37% — a fixed proportion of all possible rearrangements are always 'completely misaligned.'

Question 4

D(5) = 5!/2 = 60.

• T. True
• F. False

Answer: False

D(5) = 44, not 60. Using the recurrence with D(1)=0, D(2)=1, D(3)=2, D(4)=9: D(5) = 4·(D(4)+D(3)) = 4·(9+2) = 44. The formula D(n) = n!/2 is a common misconception. D(n)/n! converges to 1/e ≈ 0.368, which is close to but not 1/2. For n=5: D(5)/5! = 44/120 ≈ 0.367 ≈ 1/e, confirming the convergence.

Question 5

Explain why D(n) ≈ n!/e for large n, connecting the derivation to the inclusion-exclusion formula.

Model answer: Using inclusion-exclusion, D(n) = n! · Σ (−1)^k/k! for k=0 to n. This is the partial sum of the Taylor series for e⁻¹ = Σ (−1)^k/k! for k=0 to ∞. As n increases, more terms of the series are included and the sum converges to e⁻¹, giving D(n) ≈ n!/e. The convergence is fast: by n=5, the approximation is already very accurate.

The key connection is recognizing that the alternating sum from inclusion-exclusion is exactly the Taylor series for e⁻¹ truncated at n terms. This is why a combinatorial counting problem produces e as a natural constant — not because e was assumed, but because the alternating harmonic series that defines e⁻¹ arises naturally from the mechanics of counting forbidden fixed points.