Limiting Distribution of Fixed Points of a Random Function

Probability · Medium · Free problem
Pick a function $f_n: [n] \to [n]$ uniformly at random from the set of all $n^n$ functions, where $[n] = \{1, 2, \dots, n\}$. A fixed point is an index $i$ such that $f_n(i) = i$. Let $F_n$ denote the number of fixed points of $f_n$. 1. What is the exact distribution of $F_n$ for finite $n$? 2. What is the limiting distribution of $F_n$ as $n \to \infty$? That is, for any non-negative integer $k$, what does $P(F_n = k)$ converge to? 3. Compute $\displaystyle \lim_{n \to \infty} P(F_n = 3)$ to the nearest thousandth.

Open the full interactive solver, hints, and worked solution →