A note on the distribution of the sum of lengths of the initial longest increasing sequences in cycles of random permutations

Abstract

Let $S_n$ be the set of all permutations of $\{1,2,\dots ,n\}$ and let $\sigma =({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n)\in S_n$. The {\it initial longest increasing sequence} (ILIS) in $\sigma$ has length $m$ if, for $1\le m\le n-1$, ${\sigma }_1<{\sigma }_2<\dots <{\sigma }_m,{\sigma }_m>{\sigma }_{m+1}$, and has length $n$ if $\sigma =(1,2,\dots ,n)$. Let $l(\sigma )$ be the length of the ILIS in $\sigma$. We assume that $\sigma$ is represented in cycle notation, so that the first number in each cycle is the minimum number of this cycle. We also assume that $\sigma$ is chosen uniformly at random from $S_n$, i.e., with probability $1/n!$. Let $C_n(\sigma )$ be the set of all cycles of $\sigma$. In [9], T. Mansour investigated enumerative properties related to lengths of the ILIS in random permutations represented by the cycle notation. In particular, he studied the sum of the ILIS' lengths defined by $s_n={\sum }_{c\in C_n(\sigma )}l(c)$ and derived exact and asymptotic expressions for its expectation and variance. In this note, we supplement Mansour's results on $s_n$ with a limit theorem. We show that $s_n$, appropriately normalized, converges weakly to a standard normal random variable as $n\to \infty$.

8 pages