Arrow pattern avoidance in permutations: structure and enumeration
Kassie Archer, Robert P. Laudone · 2026
Read Arrow pattern avoidance in permutations: structure and enumeration by Kassie Archer, Robert P. Laudone (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-04218.txt.
Introduction
Archer and Laudone study arrow pattern avoidance in permutations, on structure and enumeration. Motivated by these results, the authors initiate a full study of arrow avoidance, proving basic results including arrow-Wilf equivalence, and listing several arrow avoidance classes. Finally, they consider avoidance of arrow-pattern pairs, focusing on cases that forbid fixed points in the core permutation.
Catalog record
| CREATOR | Kassie Archer, Robert P. Laudone |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59115 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.04218
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Arrow pattern avoidance in permutations: structure and enumeration Kassie Archer, Robert P. Laudone Abstract Arrow patterns were introduced by Berman and Tenner as a generalization of vincular patterns. They observed that arrow patterns have the potential to bridge the divide between a permutation’s cycle notation and its one-line notation; in support of this, they used arrow avoidance to enumerate shallow and cyclic shallow permutations. More recently, 321 321 -avoiding cyclic permutations were recharacterized entirely in terms of arrow avoidance. Motivated by these results, we initiate a systematic study of arrow avoidance. In this paper, we prove structural results about arrow patterns, including defining arrow-Wilf equivalence, and enumerate several arrow avoidance classes. Finally, we consider the avoidance of pairs of arrow patterns, focusing on cases that prohibit fixed points in the underlying permutation. 0 0 footnotetext: 2020 Mathematics Subject Classification. Primary 05A05 0 0 footnotetext: Keywords: Arrow patterns; pattern avoidance; permutations 1 Introduction Arrow patterns were introduced in [ 4 ] as a generalization of vincular patterns, which the authors used to characterize shallow permutations in terms of pattern avoidance. At the time, they observed that arrow patterns have the potential to bridge the divide between a permutation’s cycle notation and its one-line notation. This divide has increasingly become the focus of recent research. A central problem in this area is the enumeration of cyclic permutations whose one-line notation avoids specific patterns. For example, the authors of [ 1 , 3 ] enumerated all cyclic permutations avoiding a pair of permutations, except for the pair (132,213) . For this remaining case, bounds were established in [ 7 ] . Despite this progress, the problem of enumerating cyclic permutations whose one-line notation avoids any single pattern of size three remains open. In support of the claim in [ 4 ] , the second author of the present paper recently proved a new characterization of 321 -avoiding cyclic permutations in terms of arrow pattern avoidance [ 8 ] . This removes the need to treat pattern avoidance and cyclicity as separate conditions, reframing the problem purely in terms of avoidance. Given the results of [ 4 , 8 ] , it is highly plausible that other sets of permutations in which both the one-line and algebraic structure of the permutation are considered can be described in a similar fashion. Motivated by this potential, we initiate a systematic study of arrow avoidance. We begin in Section 2 by proving structural results about arrow patterns, defining arrow-Wilf equivalence, and connecting specific arrow patterns to vincular patterns. In Sections 3 , 4 , and 5 , we enumerate all but two of the arrow avoidance classes for arrow patterns of size 3 whose underlying string has size at most 2 and that contain a single arrow. In Section 6 , we consider the avoidance of two arrow patterns, one of which corresponds to prohibiting fixed points in the underlying permutation. Along the way, several well-known sequences emerge, which we summarize in Table 1 . We conclude in Section 7 with some open questions and conjectures. 1.1 Definitions and notation Let \mathcal{S}_{n} denote the set of permutations of [n]=\{1,2,\ldots,n\} for n\geq 1. A permutation \pi\in\mathcal{S}_{n} can be written in its one-line form as \pi=\pi_{1}\pi_{2}\ldots\pi_{n} where \pi_{i}:=\pi(i) . Alternatively, it can be written in its standard cycle form as a product of disjoint cycles where each cycle starts with its largest element and the cycles are ordered by this largest element. For example, \sigma=413526987 in one-line notation corresponds to \sigma=(3)(5214)(6)(8)(97) in its standard cycle form. The fundamental bijection \theta:\mathcal{S}_{n}\to\mathcal{S}_{n} (described in [ 9 , Page 30] ) uses both the one-line and standard cycle notation of a permutation. For a permutation \sigma\in\mathcal{S}_{n} , we obtain \theta(\sigma) by writing \sigma in its standard cycle notation and removing the parentheses to obtain a new permutation. For example, considering the same example as in the previous paragraph, \theta(413526987)=352146897. Since this map is clearly invertible, it is indeed a bijection as its name suggests. In this paper, we will often be concerned with a permutation’s inverse image under this bijection, so for ease of notation, we let \hat{\pi}=\theta^{-1}(\pi). In our example, if \pi=352146897 , then \hat{\pi}=413526987. We say that a list of positive integers a_{1}a_{2}\ldots a_{k} is order-isomorphic to a permutation \tau\in\mathcal{S}_{k} if for all r,s , we have a_{r}<a_{s} if and only if \tau_{r}<\tau_{s} . In this case, we define the reduction {\rm red}(a_{1}\ldots a_{k})=\tau. We say that a permutation \pi=\pi_{1}\cdots\pi_{n} , written in one-line notation, contains a pattern \tau=\tau_{1}\tau_{2}\ldots\tau_{k} if there are indices i_{1}<i_{2}<\cdots<i_{k} with {\rm red}(\pi_{i_{1}}\ldots\pi_{i_{k}})=\tau (that is, a subsequence of \pi is order-isomorphic to \tau ). If \pi does not contain \tau , we say \pi avoids \tau . We denote the set of permutations of size n avoiding a set of permutations \{\tau_{1},\dots,\tau_{\ell}\} by \mathcal{S}_{n}(\tau_{1},\dots,\tau_{\ell}) . Two sets of patterns S and T are called Wilf-equivalent if |\mathcal{S}_{n}(S)|=|\mathcal{S}_{n}(T)| . For example, it is well-known that when \tau\in\mathcal{S}_{3} , we have |\mathcal{S}_{n}(\tau)|=C_{n} , the n -th Catalan number, and thus all \tau\in\mathcal{S}_{3} belong to the same Wilf-equivalence class. This notion of pattern containment and avoidance can be generalized. A vincular pattern is a permutation \nu in which certain consecutive entries are marked. We use an overline for these marked entries. A permutation \pi\in\mathcal{S}_{n} contains a vincular pattern if it contains a sub-permutation in the same relative order as \nu where entries in the sub-permutation corresponding to marked entries in \nu must occur consecutively in \pi . For example, consider the vincular pattern \nu=1\overline{32} . Then, \pi=35241 avoids \nu because the only occurrence of a 132 pattern in \pi is \pi_{1}\pi_{2}\pi_{4}=354 , but the entries \pi_{2}=5 and \pi_{4}=4 do not occur consecutively. The following lemma gives the enumerations of \mathcal{S}_{n}(\nu) when \nu is size 3 with two marked entries. Lemma 1.1 ( [ 6 ] ) . For n\geq 1 , |\mathcal{S}_{n}(\nu)|=\begin{cases}B_{n}&\text{if}\;\;\nu\in\{1\overline{23},3\overline{21},\overline{12}3,\overline{32}1,1\overline{32},3\overline{12},\overline{21}3,\overline{23}1\}\\ C_{n}&\text{if}\;\;\nu\in\{2\overline{13},2\overline{31},\overline{13}2,\overline{31}2\}\end{cases} Given \pi\in\mathcal{S}_{n} with \pi=\pi_{1}\ldots\pi_{n} , the reverse of \pi , denoted \pi^{r} , is \pi_{n}\pi_{n-1}\ldots\pi_{2}\pi_{1} . The complement of \pi , denoted \pi^{c} , is (n-\pi_{1}+1)(n-\pi_{2}+1)\cdots(n-\pi_{n-1}+1)(n-\pi_{n}+1) . We note that these two operations commute, so \pi^{rc}=\pi^{cr} . For example, if \pi=623154 , then \pi^{r}=451326 , \pi^{c}=154623, and \pi^{rc}=326451 . Suppose S\subseteq[n] is a subset of the entries of \pi . Then the complement of \pi relative to S , denoted c_{S}(\pi) , is the permutation obtained from \pi by replacing the j -th smallest entry of S^{c}=[n]\setminus S , with the j -th largest entry of S^{c} . So we fix the entries of S and complement the remaining entries. We note that c_{\varnothing}(\pi)=\pi^{c} , the complement in the usual sense, and c_{[n]}(\pi)=\pi . For example, if \pi=6{\mathbf{23}}1{\mathbf{54}} and S=\{1,6\} so that S^{c}=\{2,3,4,5\} , then c_{S}(\pi)=6{\mathbf{54}}1{\mathbf{23}} . An example we will use later in this paper is c_{\{1\}}(\pi) , which we will denote by c_{1}(\pi) and call the 1 -complement of \pi . This is equal to ((n+2)-\pi_{1})((n+2)-\pi_{2})\ldots((n+2)-\pi_{j-1})1((n+2)-\pi_{j+1})\ldots((n+2)-\pi_{n}) . If \pi={\mathbf{623}}1{\mathbf{54}} , then c_{1}(\pi)={\mathbf{265}}1{\mathbf{34}} . A version of this definition of complementation was used in [ 2 ] by Bóna to understand alternating runs in permutations. Finally, many well-known and/or named sequences appear in this paper. In Table 1 , we provide the names, notation, and OEIS numbers for these sequences as reference. Notation Name Enumeration