The longest increasing subsequence in involutions avoiding 3412 and another pattern

DOI10.2478/PUMA-2022-0032MaRDI QIDQ6999672zbMATH OpenFDO

Authors Toufik Mansour, Reza Rastegar, Alexander Roitershtein, Gökhan Yıldırım

Publication date 8 April 2025

Published in PU.M.A. Pure Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2478/PUMA-2022-0032

zbMATH Keywords

generating functionlongest increasing subsequenceMotzkin pathpattern avoidancerestricted involutionUlam's problem

Mathematics Subject Classification ID

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

Review text

The authors explore the mean length of the longest increasing subsequence (LIS) in uniformly sampled involutions that avoid the pattern 3412 and another specified pattern. The study extends Ulam's classical problem to the context of pattern-avoiding involutions, providing significant insights into the combinatorial structure of such restricted permutations.\par The work employs generating functions, recursive structures, and connections to Motzkin paths to derive asymptotic results for the expected length of the LIS in various cases, and utilizes Chebyshev polynomials and continued fractions to compute generating functions for specific pattern-avoiding involutions.

This page was built for publication: The longest increasing subsequence in involutions avoiding 3412 and another pattern

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