Longest increasing subsequences in pattern-restricted permutations (Q1871367): Difference between revisions
From MaRDI portal
Set profile property. |
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
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