Problem 456

Consider an $n \times n$ table, where the rows correspond to the elements of $\{1, \ldots, n\}$ and the columns to permutations. We mark a 1 in position $(i, s)$ if the element $i$ is a fixed point of the permutation $s$. The number of 1s is counted:

- by rows: each element $i$ is a fixed point of $(n-1)!$ permutations,
- by columns: this is the total number of fixed points of all permutations.

Thus, a permutation of $\{1, \ldots, n\}$ has on average $\frac{n \cdot (n-1)!}{n!} = 1$ fixed point.