2006 Putnam A4

Let $S = \{1, 2, \dots, 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$?

对于某个整数 $n > 1$，令 $S = \{1, 2, \dots, n\}$。说一个排列

$S$ 的 $\pi$ 在 $k \in S$ 处有一个*局部最大值*，如果

(一)
$\pi(k) > \pi(k+1)$ 对于 $k=1$；

(二)
$\pi(k-1) < \pi(k)$ 和 $\pi(k) > \pi(k+1)$ 对于 $1 < k < n$；

(三)
$\pi(k-1) < \pi(k)$ 对于 $k=n$。

(例如，如果 $n=5$ 且 $\pi$ 的值为 $1, 2, 3, 4, 5$
$2, 1, 4, 5, 3$，则 $\pi$ 在 $k=1$ 处的局部最大值为 2，
$k=4$ 时局部最大值为 5。)
$S$ 排列的局部最大值的平均数量是多少，
对 $S$ 的所有排列进行平均？