Descending subsequences of random permutations (Q908915): Difference between revisions

Let \(L_ n\) be the length of the longest descending subsequence of a random permutation of 1,2,3,...,n, and let \(F_ n\) be the first element of the descending subsequences with maximal length. It is well known that \(E(L_ n)/\sqrt{n}\to c\) as \(n\to \infty\), and that \(c=2\). The author goes on to provide in this paper an elementary proof for \(c\leq 2\) by studying numerous relationships between the random variables \(L_ n\), \(F_ n\), and by obtaining combinatorial identities regarding the joint distribution of \((L_ n,F_ n)\).