Putnam 2006, Problem A-4

Let $S = \{1, 2, \ldots, n\}$ for some integer $n > 1$. Say a permutation $\pi$ of $S$ has a *local maximum* at $k \in S$ if
(i) $\pi(k) > \pi(k+1)$ for $k = 1$;
(ii) $\pi(k-1) < \pi(k)$ and $\pi(k) > \pi(k+1)$ for $1 < k < n$;
(iii) $\pi(k-1) < \pi(k)$ for $k = n$.
(For example, if $n = 5$ and $\pi$ takes values at $1, 2, 3, 4, 5$ of $2, 1, 4, 5, 3$, then $\pi$ has a local maximum of 2 at $k = 1$, and a local maximum of 5 at $k = 4$.) What is the average number of local maxima of a permutation of $S$, averaging over all permutations of $S$?

Solution:
**First solution:** By the linearity of expectation, the average number of local maxima is equal to the sum of the probability of having a local maximum at $k$ over $k = 1, \ldots, n$. For $k = 1$, this probability is $1/2$: given the pair $\{\pi(1), \pi(2)\}$, it is equally likely that $\pi(1)$ or $\pi(2)$ is bigger. Similarly, for $k = n$, the probability is $1/2$. For $1 < k < n$, the probability is $1/3$: given the pair $\{\pi(k-1), \pi(k), \pi(k+1)\}$, it is equally likely that any of the three is the largest. Thus the average number of local maxima is
$$2 \cdot \frac{1}{2} + (n-2) \cdot \frac{1}{3} = \frac{n+1}{3}.$$

**Second solution:** Another way to apply the linearity of expectation is to compute the probability that $i \in \{1, \ldots, n\}$ occurs as a local maximum. The most efficient way to do this is to imagine the permutation as consisting of the symbols $1, \ldots, n, *$ written in a circle in some order. The number $i$ occurs as a local maximum if the two symbols it is adjacent to both belong to the set $\{*, 1, \ldots, i-1\}$. There are $i(i-1)$ pairs of such symbols and $n(n-1)$ pairs in total, so the probability of