The length of the initial longest increasing sequence in a 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 ⁿ  1/j.