Descending subsequences of random permutations (Q908915): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5645369 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4192066 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A variational problem for random Young tableaux / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Descending subsequences of random permutations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ascending sequences in permutations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Longest Increasing and Decreasing Subsequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3259049 / rank | |||
Normal rank |
Latest revision as of 12:22, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Descending subsequences of random permutations |
scientific article |
Statements
Descending subsequences of random permutations (English)
0 references
1990
0 references
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)\).
0 references
longest descending subsequence
0 references
random permutation
0 references
combinatorial identities
0 references