Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences

DOI10.1016/J.AAM.2020.102002MaRDI QIDQ2300588zbMATH OpenOpenAlexWikidataFDO

Authors Toufik Mansour, Gökhan Yıldırım

Publication date 27 February 2020

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.05430

zbMATH Keywords

Chebyshev polynomialsgenerating functionslongest increasing subsequence problempattern-avoiding permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: We study the longest increasing subsequence problem for random permutations avoiding the pattern $312$ and another pattern $au$ under the uniform probability distribution. We determine the exact and asymptotic formulas for the average length of the longest increasing subsequences for such permutation classes specifically when the pattern $au$ is monotone increasing or decreasing, or any pattern of length four.

Recommendations

• Longest increasing subsequences in involutions avoiding patterns of length three
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• scientific article; zbMATH DE number 7250398
• Longest increasing subsequences in pattern-restricted permutations
• Patterns in random permutations avoiding the pattern 321

Cites work

• A microscopic model for the Burgers equation and longest increasing subsequences
• A variational problem for random Young tableaux
• Asymptotic distribution of fixed points of pattern-avoiding involutions
• Combinatorics and random matrix theory
• Combinatorics of permutations
• Commentary on ``Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem by David Aldous and Persi Diaconis
• Fixed points of 321-avoiding permutations
• scientific article; zbMATH DE number 3630761 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3373691 (Why is no real title available?)
• Increasing subsequences of random walks
• Integrable systems and combinatorial theory.
• Large deviations for permutations avoiding monotone patterns
• Lengths of monotone subsequences in a Mallows permutation
• Level-spacing distributions and the Airy kernel
• Limit theorems for longest monotone subsequences in random Mallows permutations
• Longest Increasing and Decreasing Subsequences
• Longest increasing subsequences in pattern-restricted permutations
• Longest increasing subsequences of random colored permutations
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Longest monotone subsequences and rare regions of pattern-avoiding permutations
• On Increasing Subsequences of I.I.D. Samples
• On the distribution of the length of the longest increasing subsequence of random permutations
• Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
• Pattern-avoiding permutations and Brownian excursion. II: Fixed points
• Patterns in random permutations avoiding the pattern 132
• Permutation classes
• Restricted 132-avoiding permutations
• Restricted permutations
• The Brownian limit of separable permutations
• The length of the longest increasing subsequence of a random Mallows permutation
• The longest increasing subsequence in a random permutation and a unitary random matrix model
• The surprising mathematics of longest increasing subsequences
• Universality for mathematical and physical systems

Cited in

(14)

• Longest increasing subsequences in pattern-restricted permutations
• Pattern avoiding permutations with a unique longest increasing subsequence
• Longest monotone subsequences and rare regions of pattern-avoiding permutations
• Square permutations are typically rectangular
• scientific article; zbMATH DE number 2127715 (Why is no real title available?)
• scientific article; zbMATH DE number 1515819 (Why is no real title available?)
• Variations on Hammersley’s interacting particle process
• scientific article; zbMATH DE number 7250398 (Why is no real title available?)
• Longest increasing subsequences in involutions avoiding patterns of length three
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons
• Unique longest increasing subsequences in 132-avoiding permutations
• Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three
• Permutons, meanders, and SLE-decorated Liouville quantum gravity

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences

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