Descending subsequences of random permutations
type: Item
instance of: scholarly article
title: Descending subsequences of random permutations
zbMATH Open document ID: 0694.05004
DOI: 10.1016/0097-3165(90)90022-O
author: Shaiy Pilpel
published in: Journal of Combinatorial Theory. Series A
publication date: 1990-01-01T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A19
zbMATH DE Number: 4135944
zbMATH Keywords: longest descending subsequence
zbMATH Keywords: random permutation
zbMATH Keywords: combinatorial identities
MaRDI profile type: Publication
cites work: Q5645369
cites work: Q4192066
cites work: A variational problem for random Young tableaux
cites work: Ascending sequences in permutations
cites work: Longest Increasing and Decreasing Subsequences
cites work: Q3259049
description: scientific article; zbMATH DE number 4135944