Longest increasing subsequences in pattern-restricted permutations (Q1871367): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Importer (talk | contribs)
Changed an Item
 
Property / arXiv ID
 
Property / arXiv ID: math/0304126 / rank
 
Normal rank

Latest revision as of 22:38, 18 April 2024

scientific article
Language Label Description Also known as
English
Longest increasing subsequences in pattern-restricted permutations
scientific article

    Statements

    Longest increasing subsequences in pattern-restricted permutations (English)
    0 references
    0 references
    0 references
    0 references
    7 May 2003
    0 references
    Summary: Inspired by the results of \textit{J. Baik, P. Deift} and \textit{K. Johansson} [J. Am. Math. Soc. 12, 1119-1178 (1999; Zbl 0932.05001)] on the limiting distribution of the lengths of the longest increasing subsequences in random permutations, we find those limiting distributions for pattern-restricted permutations in which the pattern is any one of the six patterns of length 3. We show that the (132)-avoiding case is identical to the distribution of heights of ordered trees, and that the (321)-avoiding case has interesting connections with a well-known theorem of \textit{P. Erdős} and \textit{G. Szekeres} [Compos. Math. 2, 463-470 (1935; Zbl 0012.27010 and JFM 61.0651.04)].
    0 references
    random permutations
    0 references

    Identifiers