Descending subsequences of random permutations

DOI10.1016/0097-3165(90)90022-OMaRDI QIDQ908915zbMATH OpenFDO

Authors Shaiy Pilpel

Publication date 1990

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(90)90022-O

zbMATH Keywords

combinatorial identitieslongest descending subsequencerandom permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19)

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)\).

Recommendations

• On increasing subsequences of random permutations
• On the distribution of the length of the longest increasing subsequence of random permutations
• The longest increasing subsequence in a random permutation and a unitary random matrix model
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• scientific article; zbMATH DE number 1047715

Cites work

• A variational problem for random Young tableaux
• Ascending sequences in permutations
• Descending subsequences of random permutations
• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• scientific article; zbMATH DE number 3630761 (Why is no real title available?)
• scientific article; zbMATH DE number 3373691 (Why is no real title available?)
• Longest Increasing and Decreasing Subsequences

Cited in

(12)

• A note on the expected length of the longest common subsequences of two i.i.d. random permutations
• Monotonous subsequences and the descent process of invariant random permutations
• The distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets
• On the Height of a Random Set of Points in a d-Dimensional Unit Cube
• Improved Bounds on Security Reductions for Discrete Log Based Signatures
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Optimal online selection of a monotone subsequence: a central limit theorem
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Untangling planar graphs from a specified vertex position-Hard cases
• An asymptotically optimal algorithm for online stacking
• Continuously increasing subsequences of random multiset permutations
• Descending subsequences of random permutations

This page was built for publication: Descending subsequences of random permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908915)