Limiting Distribution of Fixed Points of a Random Function
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 →