Permutations avoiding sets of patterns with long monotone subsequences
A permutation \(p\) contains the pattern (or subsequence) \(q=q_1 q_2 \cdots q_k\) if there is a \(k\)-element set of indices \(i_1 < i_2 < \cdots < i_k\) such that \(p_{i_r} < p_{i_s}\) if and only if \(q_r < q_s\). If \(p\) does not contain \(q\), then we say that \(p\) avoids \(q\). Let \(Av_n(q)\) be the number of permutations of length \(n\) that avoid the pattern \(q\), where the length of a permutation is the number of entries in it. In general, it is very difficult to compute the number \(Av_n(q)\), or to describe their sequence as \(n\) goes to infinity. However, the special case when \(q\) is the monotone increasing pattern of length \(k\) is much better understood; see for example [\textit{A. Regev}, Adv. Math. 41, 115--136 (1981; Zbl 0509.20009)]. Let \(A_k\) be the set of \(k\) patterns of length \(k\) that start with an increasing subsequence of length \(k-1\) and let \(A_{k,i} = A_k \setminus \{12\cdots (i-1)(i+1)\cdots ki\}\), that is, the set \(A_k\) with its elements ending in \(i\) removed. We say \(p\) avoids \(A_{k,i}\) if \(p\) avoids all patterns in \(A_{k,i}\) and we write \(Av_n(A_{k, i})\) for the number of such permutations of length \(n\). The goal of this paper is to determine the exponential growth rate \(L(A_{k,i})\) for the sequence \(Av_n(A_{k,i})\), for each \(i\leq k\). For \(2\leq i \leq k-1\), it is proven in Theorem 2.1 that \(L(A_{k,i}) = (k-2)^2\), so avoiding \(A_{k,i}\) is just as hard as avoiding \(12\cdots (k-1)\). For \(i=k\), it is proven in Theorem 3.1 that \(L(A_{k,k}) = (k-2)^2+1\). Case \(i=1\) is the most difficult case and thus a few conjectures and some experimental evidence are provided in this paper.
- Asymptotic values for degrees associated with strips of Young diagrams
- Combinatorics of permutations
- Five subsets of permutations enumerated as weak sorting permutations
- Generating permutations with restricted containers
- GFUN
- scientific article; zbMATH DE number 1601795 (Why is no real title available?)
- On the growth of merges and staircases of permutation classes
- Permutation classes
- The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns
- Supercritical sequences, and the nonrationality of most principal permutation classes
- Permutations with exactly one copy of a monotone pattern of length \(k\), and a generalization
- Stieltjes moment sequences for pattern-avoiding permutations
- Pattern avoiding permutations with a unique longest increasing subsequence
- Schur-concavity for avoidance of increasing subsequences in block-ascending permutations
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- Permutation classes of polynomial growth
- On three different notions of monotone subsequences
- Permutation patterns are hard to count
- scientific article; zbMATH DE number 1447312 (Why is no real title available?)
- Counting crucial permutations with respect to monotone patterns
- Growth rates for subclasses of Av(321)
- Long increasing subsequences and non-algebraicity
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- Combinatorial exploration: an algorithmic framework for enumeration
This page was built for publication: Permutations avoiding sets of patterns with long monotone subsequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2100048)
