Fixed Point Probability in a Random Permutation
Pick a uniformly random permutation $f: [n] \rightarrow [n]$, where $[n] = \{1, 2, \ldots, n\}$. We call index $i$ a fixed point if $f(i) = i$ -- it maps to itself.
With $n = 10$, what is the probability that $1$ is a fixed point but $2$ is not?
Hints
- Let $F_i$ be the event that $i$ is a fixed point. Express the target probability as $P(F_1 \cap F_2^c)$, and note that $P(F_1 \cap F_2^c) = P(F_1) - P(F_1 \cap F_2)$.
- Each event $P(F_1)$ and $P(F_1 \cap F_2)$ is easy to compute by counting permutations: fixing $k$ specific elements leaves $(n-k)!$ free arrangements.
- You get $P(F_1) = 1/n$ and $P(F_1 \cap F_2) = 1/(n(n-1))$; subtract to get the general formula $\frac{n-2}{n(n-1)}$, then plug in $n = 10$.
Worked Solution
How to Think About It: This is a counting problem in disguise. You have $n!$ equally likely permutations, and you want to count how many have $f(1) = 1$ but $f(2) \neq 2$. The clean way to do this: count the ones with $f(1) = 1$, then subtract the ones where both $f(1) = 1$ and $f(2) = 2$. That is just inclusion-exclusion on two events -- a one-liner once you see it. The answer should be noticeably less than $1/n$ (the probability that $1$ alone is fixed) because we are restricting to a subset.
Quick Estimate: With $n = 10$, the probability that $1$ is fixed is $1/10 = 0.10$. Given that $1$ is fixed, element $2$ maps to one of the remaining 9 positions, and exactly one of those is $f(2) = 2$, so the conditional probability that $2$ is also fixed is $1/9$. The probability we want is $P(F_1) - P(F_1 \cap F_2) = 1/10 - 1/90 = 9/90 - 1/90 = 8/90 = 4/45 \approx 0.089$. Ballpark: just under 9%.
Approach: Differencing (inclusion-exclusion on two events), confirmed by a direct combinatorial count.
Formal Solution:
Let $F_i$ denote the event that $i$ is a fixed point of $f$. We want $P(F_1 \cap F_2^c)$.
Since $F_1 \cap F_2^c$ and $F_1 \cap F_2$ partition $F_1$:
$$P(F_1 \cap F_2^c) = P(F_1) - P(F_1 \cap F_2)$$
All $n!$ permutations are equally likely, so we count favorable outcomes.
- $|F_1|$: fix $f(1) = 1$, freely permute the remaining $n-1$ elements. Count: $(n-1)!$
- $|F_1 \cap F_2|$: fix $f(1) = 1$ and $f(2) = 2$, freely permute the remaining $n-2$ elements. Count: $(n-2)!$
Converting to probabilities:
$$P(F_1) = \frac{(n-1)!}{n!} = \frac{1}{n}, \qquad P(F_1 \cap F_2) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)}$$
Therefore:
$$P(F_1 \cap F_2^c) = \frac{1}{n} - \frac{1}{n(n-1)} = \frac{n-1}{n(n-1)} - \frac{1}{n(n-1)} = \frac{n-2}{n(n-1)}$$
Alternative (direct count): Among all $n(n-1)$ ordered pairs $(f(1), f(2))$ with $f(1) \neq f(2)$, exactly one choice satisfies $f(1) = 1$ (element 1 is fixed), and then $f(2)$ can be any of the $n-2$ values that are not $1$ or $2$. So the probability is directly $\frac{n-2}{n(n-1)}$, confirming the result.
Answer: With $n = 10$:
$$P(F_1 \cap F_2^c) = \frac{10-2}{10 \cdot 9} = \frac{8}{90} = \frac{4}{45}$$
Intuition
The core lesson here is that conditioning on a fixed point barely affects the chance that any other specific element is also fixed. The probability that element 1 is fixed is $1/n$. Given that, the conditional probability that element 2 is also fixed is $1/(n-1)$ -- just slightly higher than $1/n$. This is the hallmark of exchangeability: the joint distribution of fixed-point indicators is symmetric across positions, and knowing one position is fixed gives you only mild information about the others.
This structure shows up constantly in combinatorics and probability: the inclusion-exclusion technique used here -- P(A and not B) = P(A) - P(A and B) -- is one of the most reusable tools in the kit. In quant interviews, a version of this reasoning appears in derangement problems (zero fixed points), ballot problems, and collision probability calculations. When you see 'exactly this set of conditions holds but not that one,' reach for differencing before reaching for anything fancier.