Permutation Statistics: Records & Fixed Points

Hard4–5 hrsPermutationsFixed PointsRecordsCycle StructureStirling Numbers

Overview

Permutation statistics are among the most beautiful results in combinatorics. Three key facts: (1) the expected number of records equals Hₙ, provable by a one-line indicator argument, (2) the expected number of fixed points equals exactly 1 regardless of n, and (3) the probability of no fixed point (derangement) converges rapidly to 1/e. These results appear directly in trading interviews — records are related to optimal stopping (secretary problem), cycles appear in the 100-prisoners problem, and derangements appear whenever you ask 'what's the probability that no pairing is correct?'

How to Recognize

→'How many left-to-right maxima (records) in a random permutation?'
→'P(no element is in its original position)' — derangements
→'Expected number of cycles in a random permutation'
→Any question about structure of a uniformly random permutation
→Interviewers asking about permutation-based probability

Step-by-Step Approach

1.Use indicator variables: Iₖ = 1 if position k is a record → P(Iₖ=1) = 1/k by symmetry
2.E[# records] = Σ 1/k = Hₙ (harmonic number)
3.E[# fixed points] = 1 (regardless of n!)
4.E[# cycles] = Hₙ (same as records — surprising connection)
5.P(derangement) → 1/e via inclusion-exclusion or Poisson approximation

Key Formulas

E[\text{records in perm of }n] = H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}

E[\text{fixed points}] = 1

for any

n \ge 1

E[\text{cycles in random perm of }n] = H_n

P(\text{derangement}) = \sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1} \approx 0.368

Worked Examples

0Quick Example

Shuffle 10 cards. E[records] = H₁₀ = 1+1/2+...+1/10 ≈ 2.93. E[fixed points] = 1. P(no fixed points) → 1/e. E[cycles] = H₁₀ ≈ 2.93.

Problem

A uniformly random permutation of n elements is chosen. How many cycles does it have, in expectation? Prove it.

Solution

Let $C_k$ = indicator that element k starts a new cycle (i.e., k is the minimum element of its cycle).

E[# cycles] = Σₖ₌₁ⁿ P(k is cycle minimum).

In the cycle containing k, k is the minimum iff k comes 'first' in the cycle. By symmetry among the elements in the cycle, P(k is minimum of its cycle) = 1/(cycle length).

But E[1/(cycle length containing k)] averaged over all permutations equals... let's use another approach.

Bijection with records: there's a bijection (Foata's correspondence) between permutations of [n] and themselves that maps 'cycle minima' to 'left-to-right minima' (records of the INVERSE). So E[cycles] = E[records] = Hₙ.

Direct proof: P(element k is a cycle minimum) = P(k is smallest of {k, next, next...}) = 1/k if we think of elements in cycle order. Summing: E[cycles] = Σ 1/k = Hₙ.

Answer

$E[\text{cycles in random permutation of }n] = H_n \approx \ln n + 0.577$ . For n=100: ≈5.19 cycles on average.

Common Mistakes

!
Confusing records and records from the LEFT. 'Record' typically means left-to-right maximum (each element is larger than ALL previous). A different count is records from the right.
!
Thinking P(position k is a record) depends on the distribution — it only requires the permutation to be UNIFORM. Any uniform shuffle gives P(position k is record) = 1/k.
!
Derangements and fixed-point Poisson approximation. For large n, the number of fixed points is approximately Poisson(1). P(k fixed points) ≈ e⁻¹/k!.

Practice Problems

Click "Show Answer" to reveal

20 people exchange Secret Santa gifts randomly (uniform random permutation, no self-gifting — a derangement). E[people who correctly 'match' with their original intended recipient] = ?

Hint: Wait — a derangement has NO fixed points. But here 'match' might mean something else. Re-read: if we simply shuffle 20 gifts randomly (allowing self-gifting), E[self-gifts] = 1. But in a derangement, E[self-gifts] = 0 by definition.

In the 100-prisoners problem, what strategy should prisoners use if only 40 of them (not 50) are allowed to look in boxes? What is P(all survive)?

Hint: Now need: max cycle length ≤ 40. P(max cycle > 40) = Σₖ₌₄₁¹⁰⁰ 1/k = H₁₀₀ - H₄₀.

Back to Study Plan

Inclusion-Exclusion Principle Generating Functions