Descending subsequences of random permutations

Abstract

Given a random permutation of the numbers 1, 2, ..., n, let Ln be the length of the longest descending subsequence of this permutation. Let Fn be the minimal header (first element) of the descending subsequences having maximal length. It is known that ELn n→n→∞c and that c = 2. However, the proofs that c = 2 are far from elementary and involve limit processes. Several relationships between these two random variables are established, namely, ELn = Σj = 1nP(Fj = j) and P(Fn + 1 = n + 1) = 1 - E Fn n + 1. Some other combinatorial identities regarding the distribution of the bivariate random variable (Ln, Fn) are also proved. The definition of Fn is generalized, characterizing the elements appearing at the first row and first column of the Young tableau corresponding to a given permutation. As a result, an elementary proof for c ≤ 2 is constructed. © 1990.