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

Toufik Mansour; Gökhan Yıldırım

doi:10.1016/j.aam.2020.102002

paper

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

arXiv:1808.05430 · doi:10.1016/j.aam.2020.102002

Abstract

We study the longest increasing subsequence problem for random permutations avoiding the pattern $312$ and another pattern $τ$ 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 $τ$ is monotone increasing or decreasing, or any pattern of length four.

14 pages, 1 table, Lemma 2.1 added, some additions and minor corrections made