# The length of the initial longest increasing sequence in a permutation

## DOI:

https://doi.org/10.26493/2590-9770.1516.96f## Keywords:

Generating function, harmonic number, initial longest increasing sequence, permutation## Abstract

Let *S*_{n} be the set of all permutations of {1, 2, …, *n*} represented in cycle notation. Define *a*_{n, m} to be the number of *π* ∈ *S*_{n} such that the length of the *initial longest increasing sequence* (ILIS) in *π* is at most *m*. For fixed *m*, we find the exponential generating function for the sequence *a*_{n, m}, and give an asymptotic formula for *a*_{n, m} when *n* → ∞. Moreover, we show that the expected value of the total ILIS in all cycles of *π* over all permutations of *S*_{n} is asymptotic to *e *∑_{j=1}^{ n }1/j.