Given an ordered $n$-tuple $A=(a_1,a_2,\cdots ,a_n)$ of real numbers, where $n\ge 2$, we define $b_k=\max{a_1,\ldots a_k}$ for each k. We define $B=(b_1,b_2,\cdots ,b_n)$ to be the “innovated tuple” of $A$. The number of distinct elements in $B$ is called the “innovated degree” of $A$. Consider all permutations of $1,2,\ldots ,n$ as an ordered $n$-tuple. Find the arithmetic mean of the first term of the permutations whose innovated degrees are all equal to $2$
Problem
Source: Chinese Mathematical Olympiad 2000 Problem 4
Tags: combinatorics, permutations, permutation statistics
JBL
19.08.2013 22:05
The "innovated degree" is usually known as the number of left-to-right maxima of the permutation. A permutation of $\{1,\ldots,n\}$ has exactly two left-to-right maxima if and only if its first entry $k$ satisfies $k<n$ and all entries in the permutation between (in position) $k$ and $n$ have value less than $k$. Thus, the number of permutations with exactly two left-to-right maxima and first entry $k$ is \begin{align*} \sum_{j=0}^{k-1} \binom{k-1}{j}j!(n-j-2)! &= (k-1)!(n-k-1)!\sum_{j=0}^{k-1} \binom{n-j-2}{n-k-1} \\ &= (k-1)!(n-k-1)!\binom{n-1}{n-k}\\ &= \frac{(n-1)!}{n-k} \end{align*} (possibly there was a cleverer way to see this). Consequently, the average in question is (canceling common factors) \[ \frac{\sum_{k=1}^{n-1}\frac{k}{n-k}}{\sum_{k=1}^{n-1}\frac{1}{n-k}}=n-\frac{n-1}{H_{n-1}}.\]
MellowMelon
19.08.2013 22:14
Another way to obtain the $\frac{(n-1)!}{n-k}$ is to note that among all $(n-1)!$ permutations with $k$ in the first permutation, we need only the ones with $n$ coming before $k+1, k+2, \ldots, n-1$. Consider the orbits obtained by applying the cycle $(n, k+1, k+2, \ldots, n-1)$. All these orbits have size $n-k$, and exactly one element in each orbit satisfies the conditions we want.