high-water mark distribution Given a sequence of values ${a_k}_{k=1}^n$, the high-water marks are the values at which the running maximum increases. For example, given a sequence $(3,5,7,8,8,5,7,9,2,5)$ with running maxima $(3,5,7,8,8,8,9,9,9)$, the high-water marks are $(3,5,7,8,9)$, which occur at $k=1, 2, 3, 4, 8$. For every sequence $a_k$ there is a number of high-water marks $N_{a_k}$ Consider a set $\sigma$ of all permutations of $n$ numbers $(1, \dots, n)$. Does anybody knows the analytical expression for the distribution of the number of high-water marks ($N_{a\in \sigma}$)? For example, if $n=3$ $1,2,3 \rightarrow 3$ $1,3,2 \rightarrow 2$ $2,1,3 \rightarrow 2$ $2,3,1 \rightarrow 2$ $3,1,2 \rightarrow 1$ $3,2,1 \rightarrow 1$ and the distribution is $\left( \frac{2}{3!},\frac{3}{3!},\frac{1}{3!} \right)$. Any references would be appreciated.

Consider the cycle representation of a permutation (including the trivial one-element cycles). In each cycle, bring the greatest element to the front. Then order the cycles by these greatest elements, smallest first. If you now write down this cycle representation, ignore the parentheses and consider the resulting string as representing a permutation, precisely the greatest elements of the cycles are high-water marks in this permutation.

This establishes a bijection of the symmetric group with itself that maps between numbers of cycles and numbers of high-water marks. Thus the distribution of the number of high-water marks is the distribution of the number of cycles. This is given by the unsigned Stirling numbers of the first kind.