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
| CREATOR | Michael Waite |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20164 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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