Permutations with a fixed number of occurrences of a pattern: a case generalizing 231

Michael Waite · 2026

Read Permutations with a fixed number of occurrences of a pattern: a case generalizing 231 by Michael Waite (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21625.txt.

Introduction

Waite counts permutations by how many times a fixed pattern occurs inside them. For a chosen family of patterns, Waite shows the count with r occurrences is asymptotically n to the r times the count that avoids the pattern entirely. This settles part of a conjecture by Conway and Guttman. The work focuses on a case that generalizes the pattern 231. Waite also uses the asymptotics to prove that certain ordinary generating functions for these counts are neither rational nor algebraic.

Catalog record

CREATORMichael Waite
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20164
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21625

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Permutations with a fixed number of occurrences of a pattern: a case generalizing 231 Michael Waite Abstract . We determine a set of permutation patterns q q so that the number of permutations with r r occurrences of q q is asymptotically n r n^{r} times the number of permutations avoiding q q , partially settling a conjecture of Conway and Guttman. We also use these asymptotics to prove nonrationality and nonalgebraicity for certain ordinary generating functions for permutations with r r copies of a pattern. 1. Introduction We say that a permutation p contains a pattern q=q_{1}...q_{k} if there is a subsequence n_{1},...,n_{k} so that p_{n_{i}}<p_{n_{j}} if and only if q_{i}<q_{j} . We say that p contains r copies of q if there are r different such subsequences n_{1},...,n_{k} . We denote the set of permutations of length n that avoid q as S_{n}(q) , and we denote the set of permutations with r copies of q as S_{n,r}(q) . It is well-known that |S_{n}(321)|=|S_{n}(231)|=\frac{1}{n+1}{2n\choose n} , which is the n th Catalan number. However, it is not true that |S_{n,r}(321)|=|S_{n,r}(231)| for r\geq 1 . It is known due to Noonan [ 8 ] that |S_{n,1}(321)|=\frac{3}{n}{2n\choose n+3} and it is known due to Bóna [ 3 ] that |S_{n,1}(231)|={2n-3\choose n-3} . Enumerations of |S_{n,r}(q)| have been done for small values of r for the length 3 patterns, but a perhaps more interesting question is what happens as we vary r . It is known due to Bóna [ 4 ] that there is some constant C so that |S_{n,r}(231)|\sim C\frac{4^{n}}{n^{3/2-r}} , and the present author [ 9 ] has recently shown that there is a constant C so that |S_{n,r}(321)|\sim C\frac{4^{n}}{n^{3/2}} , and moreover that for any permutation q it is true that |S_{n,r}(321\ominus q)|\sim C|S_{n}(321\ominus q)| . Recently, Conway and Guttman [ 6 ] have found substantial numerical evidence for the asymptotics of |S_{n,r}(q)| where q is of length 4 . For five of the seven different classes, they have conjectured that |S_{n,r}(q)|\sim Cn^{r}|S_{n}(q)| In this paper, we will find a set of patterns so that there is a constant C so that |S_{n,r}(q)|\sim Cn^{r}|S_{n}(q)| , as is known to be true for q=231 . In Section 2, we will construct an injection that gives us the desired upper bound, and in Section 3 , we will construct an injection that gives us the desired lower bound. In Section 4 , we state the main result of the paper, combining the necessary conditions on the pattern q from the upper bound and from the lower bound. In Section 5 we will apply these results for patterns where the asymptotics are known, and obtain new results on the nonrationality and nonalgebraicity of the generating functions for permutations with r copies of these patterns. Finally, in Section 6 we return to the conjecture of Conway and Guttmann [ 6 ] and discuss which cases are remaining. 2. A Lower Bound First, we need a definition. Definition 2.1 . Suppose n\geq k . Let \mathcal{I}_{n,k} denote the set of size k subsets of the set [n]=\{1,2,...,n\} . Now, we will state and prove the main result of this section. Theorem 2.2 . Let q be a permutation of length m which is indecomposable, and is of the form q_{1}\ominus...\ominus q_{k} for some k\geq 2 where all of the q_{i} are skew-indecomposable and q_{2},...,q_{k-1} are not 1 . Let q_{1} be of length \ell . Suppose r\geq 1 . Then there is an injection \phi:\mathcal{I}_{n-rm-\ell+1,r}\times S_{n-rm-\ell}(q)\hookrightarrow S_{n,r}(q) for n\geq rm . Proof. Let p\in S_{n-rm-\ell}(q) and let S\in\mathcal{I}_{n-rm-\ell+1,r} . Let s_{1},...,s_{r} be the entries in S in increasing order. Replace p by q_{1}\oplus p\in Av_{n-rm}(q) , so that we can assume that p begins with a copy of q_{1} , and replace each s_{i} by s_{i}+\ell . Our main idea is that we will insert a copy of q in certain blocks of consecutive values at each of the positions s_{1},...,s_{r} in p , and we will choose these blocks of values in such a way as to not create extra q patterns. Now we will define these blocks of values. Let B_{1} consist of q_{1} and all of the values of q_{2} except for the smallest value. For 2\leq i\leq k-2 , let B_{i} be the set of values consisting of the smallest value of q_{i} and all of the values of q_{i+1} except for the smallest value. Let B_{k-1} be the set of values consisting of the smallest value of q_{k-1} and all of q_{k} . For 1\leq i\leq k let b_{i}=|B_{i}| . Now we will insert copies of q iteratively starting at s_{1} . For 1\leq i\leq k-1 let a_{i} be the largest entry that is the smallest entry of a q_{1}\ominus...\ominus q_{i} pattern that is entirely to the left of s_{1} . Insert a copy of q in position s_{1} with the values of B_{i} in between a_{i} and the next larger entry. Let L_{1} be the subsequence of entries to the left of s_{1} with value greater than a_{1} . For 2\leq i\leq k-1 , let L_{i} be the subsequence of entries to the left of s_{1} with value greater than a_{i} , and less than or equal to a_{i-1} . Let L_{k} be the subsequence of entries to the left of s_{1} with value less than or equal to a_{k-1} . Likewise define R_{1} , …, R_{k} for entries to the right of s_{1} . L_{4} L_{3} L_{2} L_{1} B_{3} B_{2} B_{1} R_{4} R_{3} R_{2} R_{1} a_{1} a_{2} a_{3} Figure 1. Insertion of a q pattern at position s_{1} , where k=4 . For 1\leq i\leq k-1 , by the definition of a_{i} then the entries contained in L_{1}\cup...\cup L_{i} cannot contain a q_{1}\ominus...\ominus q_{i} . Because p does not contain any q patterns with entries to the right of s_{1} , then for 2\leq i\leq k the entries contained in R_{i}\cup...\cup R_{k} cannot contain a q_{i}\ominus...\ominus q_{k} pattern. Say there were a q pattern with some entries in the B_{i} blocks and some entries not in the B_{i} blocks. Let m be minimum so that there are some entries in this q pattern in B_{m} , and M be maximum so that there are some entries in this q pattern in B_{M} . Since L_{1}\cup...\cup L_{m} cannot contain q_{1}\ominus...\ominus q_{m} , then the q_{m} in the q pattern must have some entries in B_{m} . Since R_{M+1}\cup...\cup R_{k} cannot contain any q_{M+1}\ominus...\ominus q_{k} pattern, then the q_{M+1} in the q pattern must have some entries in B_{M} . The possible ways to place a q_{i} for m\leq i\leq M+1 so that not all of the entries are in a B_{j} for some j now must be either with some entries to the left of B_{m} and some entries in B_{m} , some entries in B_{m} and some entries in B_{m+1} , …, some entries in B_{M-1} and some entries in B_{M} , or some entries in B_{M} and some entries to the right of B_{M} , or if m=1 then all of q_{m} may be entirely in B_{m} or if M=k then all of q_{M} may be entirely in B_{M} . There are M-m+2 of

Read the complete text