MathDB

Let

S=\{1,2\dots,n\}

for some integer

n>1.

Say a permutation

\pi

S

has a local maximum at

k\in S

\begin{array}{ccc}\text{(i)}&\pi(k)>\pi(k+1)&\text{for }k=1\\ \text{(ii)}&\pi(k-1)<\pi(k)\text{ and }\pi(k)>\pi(k+1)&\text{for }1<k<n\\ \text{(iii)}&\pi(k-1)M\pi(k)&\text{for }k=n\end{array}

(For example, if

n=5

and

\pi

takes values at

1,2,3,4,5

2,1,4,5,3,

then

\pi

has a local maximum of

2

k=1,

and a local maximum at

k-4.

) What is the average number of local maxima of a permutation of

S,

averaging over all permuatations of

S?

Problem Statement