Longest increasing subsequences in involutions avoiding patterns of length three

Authors : Toufik Mansour, Gökhan Yildirim

Pages : 2183-2192

View : 19 | Download : 8

Publication Date : 9999-12-31

Article Type : Makaleler

Abstract :We study the longest increasing subsequences in random involutions that avoid the patterns of length three 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.
Keywords : Pattern-avoidance, involutions, longest increasing subsequences, Chebyshev polynomials, generating functions