Arrow pattern avoidance in permutations: structure and enumeration

Imagine you have a deck of numbered cards, from 1 to $n$ . A permutation is just a specific order in which you lay these cards out on a table. Mathematicians love studying these arrangements because they hide deep secrets about structure and order.

Usually, mathematicians look for "forbidden shapes" in these card layouts. For example, they might say, "No three cards can be arranged in a 'low-high-low' pattern." This is called pattern avoidance.

This paper introduces a new, more magical way of looking at these cards. The authors, Kassie Archer and Robert Laudone, are studying something called Arrow Patterns.

The Magic Trick: Two Ways to See the Cards

To understand Arrow Patterns, you need to know that every deck of cards has two secret identities:

The Line-Up (One-line notation): This is how the cards sit on the table, left to right. (e.g., 3, 1, 4, 2).
The Circle Dance (Cycle notation): This is how the cards are secretly connected in loops. Imagine card 3 points to card 1, card 1 points to card 4, and card 4 points back to 3. They form a circle.

Usually, these two views are treated as separate things. But Arrow Patterns are like a special pair of glasses that let you see both the Line-Up and the Circle Dance at the same time.

An "Arrow Pattern" is a rule that says: "Look for a specific shape in the Line-Up, but also check if the cards in that shape are connected by a specific arrow in the Circle Dance."

The Game: Avoiding the Arrows

The authors play a game of "Don't Do It!" They ask: How many ways can we arrange the cards so that we never accidentally create a forbidden Arrow Pattern?

Think of it like a game of musical chairs with strict rules.

The Players: The numbers 1 through $n$ .
The Rule: You cannot arrange them in a way that matches a specific "Arrow Pattern."
The Goal: Count how many safe arrangements exist.

What They Discovered

The paper is a massive catalog of these games. The authors broke them down into different levels of difficulty:

1. The Simple Rules (Size 1 and 2)
They started with the easiest rules.

Example: "Don't let a card point to itself in the Circle Dance."
- Result: This is a famous math problem called "Derangements." It's like a Secret Santa where no one can pick their own name. The number of ways to do this is a well-known sequence.
Example: "Don't let a small card point to a bigger card in a specific way."
- Result: This leads to the Bell Numbers, which count how many ways you can split a group of friends into different teams.

2. The Medium Rules (Size 3)
They moved on to slightly more complex patterns involving three cards.

Some patterns were so restrictive that there was only one way to arrange the cards (like lining them up perfectly in order).
Others led to the Catalan Numbers, a famous sequence that pops up everywhere in math (like counting valid parenthesis combinations or mountain ranges).
They found that some different-looking rules actually produce the exact same number of solutions. They call this "Arrow-Wilf Equivalence." It's like discovering that two different recipes, using different ingredients, somehow result in the exact same number of cookies.

3. The Double Trouble (Avoiding Two Rules at Once)
The authors also looked at what happens when you have to avoid two forbidden patterns simultaneously.

The Twist: One of the rules they added was "No fixed points." This means no card can point to itself in the Circle Dance.
Result: This combination created some very rare and beautiful number sequences, like the Riordan Numbers and Gould Numbers. These are like finding a hidden treasure map in the math world.

Why Does This Matter?

You might ask, "Who cares about counting card arrangements?"

The authors explain that Arrow Patterns are a bridge.

For a long time, mathematicians struggled to count "Cyclic Permutations" (arrangements that form one giant loop) while also avoiding certain shapes. It was like trying to solve a puzzle where the pieces kept changing shape.
By using Arrow Patterns, they can describe these complex problems using simple "avoidance" rules.
The Big Hope: They believe this new tool might finally help them solve a decades-old mystery: counting permutations that avoid the "321" pattern while being cyclic. This is currently a very hard problem, and Arrow Patterns might be the key to unlocking it.

The Takeaway

Think of this paper as a new language for describing how things are connected.

Old Language: "Look at the line, then look at the circles, then try to match them." (Confusing!)
New Language (Arrow Patterns): "Look for this specific arrow shape." (Simple!)

The authors have built a dictionary of these shapes, showing us which ones are easy to avoid, which ones are impossible, and which ones lead to famous number sequences. They've opened a door that might lead to solving some of the most stubborn puzzles in the world of permutations.

Here is a detailed technical summary of the paper "Arrow pattern avoidance in permutations: structure and enumeration" by Kassie Archer and Robert P. Laudone.

1. Problem Statement and Motivation

The paper addresses the enumeration of permutations that avoid specific arrow patterns. Arrow patterns, introduced by Berman and Tenner, generalize vincular patterns (where certain adjacent entries must be consecutive) by incorporating constraints based on a permutation's cycle structure.

The Core Divide: A fundamental challenge in permutation combinatorics is bridging the gap between a permutation's one-line notation (linear order) and its cycle notation (algebraic structure).
The Gap: While vincular patterns constrain the linear order, they do not inherently capture cycle properties. Arrow patterns were designed to "bridge" this divide by requiring that specific elements map to one another within the cycle decomposition.
Specific Goal: The authors initiate a systematic study of arrow avoidance to:
1. Establish structural properties and equivalences (arrow-Wilf equivalence).
2. Enumerate permutations avoiding arrow patterns of size 3 (where the underlying string has size $\le 2$ and contains a single arrow).
3. Investigate pairs of arrow patterns, specifically those that prohibit fixed points (derangements).

2. Methodology and Definitions

2.1 Fundamental Definitions

Permutation Notation: The authors utilize the fundamental bijection $\theta: S_n \to S_n$ . For a permutation $\sigma$ , $\theta(\sigma)$ is obtained by writing $\sigma$ in standard cycle notation (cycles start with their largest element, ordered by these maxima) and removing parentheses.
The Inverse Map: The authors define $\hat{\pi} = \theta^{-1}(\pi)$ . This map is crucial because arrow patterns impose conditions on $\hat{\pi}$ .
Arrow Pattern Containment: A permutation $\pi$ $π$ contains an arrow pattern $\alpha = (\nu; H)$ $α = (ν; H)$ if:
1. There exists a subsequence in $\pi$ order-isomorphic to the string $\nu$ .
2. For every arrow $b_i \to c_i$ in $H$ , the element corresponding to $b_i$ in the subsequence maps to the element corresponding to $c_i$ in the cycle decomposition of $\hat{\pi}$ .
Avoidance: $\pi$ avoids $\alpha$ if it contains no such occurrence.

2.2 Structural Tools

Arrow-Wilf Equivalence: Two arrow patterns are equivalent if they are avoided by the same number of permutations for all $n$ .
Reduction to Vincular Patterns: The paper proves that certain arrow patterns are equivalent to classical vincular patterns. Specifically, if an arrow $b \to \nu_i$ exists where $b$ is larger than $\nu_i$ , the condition forces $\nu_i$ to immediately follow $b$ in the linear representation, effectively turning the arrow pattern into a vincular pattern with a bar over $b$ and $\nu_i$ .
Complementation and Reversal: The authors utilize operations like the $1 $-complement ($ c_1(\pi)$) and standard reversal/complement to establish equivalences between different arrow patterns.

3. Key Contributions and Results

The paper is structured into sections enumerating specific classes of arrow patterns. The results are summarized in Tables 2 through 6.

3.1 Small Patterns (Size 1 and 2)

The authors first enumerate permutations avoiding patterns in $A_1$ and $A_2$ (patterns with underlying string size 1 or 2).

Derangements: Avoiding $(1; 1 \to 1)$ corresponds exactly to derangements ( $d_n$ ), as it forbids fixed points in $\hat{\pi}$ .
Bell Numbers: Avoiding $(12; 1 \to 2)$ forces all cycles in $\hat{\pi}$ to be decreasing, establishing a bijection with set partitions, yielding the Bell numbers ( $B_n$ ).
Catalan and Schröder Numbers: Various patterns map to Catalan numbers ( $C_n$ ) and Large Schröder numbers ( $S_n$ ). For instance, avoiding $(12; 3 \to 1)$ is equivalent to avoiding the vincular pattern $312 $, yielding$ C_n$.

3.2 Patterns of Size 3

The bulk of the paper enumerates patterns $\alpha = (\nu; H)$ where $|\nu| \in \{1, 2\}$ and $|H|=1$ .

Case $(12; b \to c)$ :
- $(12; 1 \to 2) \implies B_n$ (Bell numbers).
- $(12; 1 \to 3) \implies S_{n-1}$ (Large Schröder numbers).
- $(12; 3 \to 1) \implies C_n$ (Catalan numbers).
- $(12; 2 \to 3) \implies 2B_{n-1}$ .
Case $(21; b \to c)$ :
- $(21; 1 \to 3) \implies 2^{n-1}$ (Bijection with compositions of $n$ ).
- $(21; 2 \to 3) \implies$ A complex recurrence involving 231-avoiding permutations with no fixed points.
Case $(13; b \to c)$ :
- $(13; 1 \to 2), (13; 2 \to 1), (13; 3 \to 2) \implies B_n$ .
- $(13; 2 \to 3)$ and $(13; 2 \to 2)$ yield complex recurrences involving Stirling numbers of the second kind and derangements.

3.3 Avoiding Pairs (Prohibiting Fixed Points)

Section 6 considers the simultaneous avoidance of an arrow pattern $\alpha$ and the pattern $\beta = (1; 1 \to 1)$ (which forces $\hat{\pi}$ to be a derangement).

2-Associated Bell Numbers: Avoiding $(12; 1 \to 2)$ and fixed points yields the 2-associated Bell numbers ( $B_{n \ge 2}$ ), counting set partitions with no singletons.
Riordan Numbers: Avoiding $(12; 3 \to 1)$ and fixed points yields the Riordan numbers ( $r_n$ ), providing a new combinatorial interpretation for this sequence.
Gould Numbers: Avoiding $(12; 2 \to 3)$ and fixed points yields the Gould numbers ( $G_{n-2}$ ).
Recurrences: The authors derive specific recurrence relations for these classes, often linking them to convolutions of derangements and other known sequences.

4. Significance and Impact

Unification of Structures: The paper successfully demonstrates that arrow patterns provide a unified framework to describe sets of permutations defined by both linear order (one-line notation) and algebraic structure (cycle notation).
New Combinatorial Interpretations: The work provides novel combinatorial interpretations for well-known sequences (Riordan, Gould, 2-associated Bell) in terms of arrow avoidance, expanding the catalog of pattern-avoiding classes.
Systematic Enumeration: By classifying almost all arrow patterns of size 3 with small underlying strings, the paper establishes a foundational taxonomy for this field.
Future Directions: The authors identify open problems, including the enumeration of patterns with $|\nu| > 2$ or $|H| > 2$ . They also conjecture connections to Fibonacci and Motzkin numbers when combining arrow avoidance with classical pattern avoidance (e.g., avoiding $321 $and$ (12; 1 \to 2)$).
Cyclic Permutations: The introduction highlights that arrow avoidance is a powerful tool for characterizing cyclic permutations (e.g., 321-avoiding cyclic permutations), suggesting that this methodology could solve long-standing open problems regarding the enumeration of cyclic permutations avoiding specific patterns.

In summary, Archer and Laudone have laid the groundwork for a systematic theory of arrow pattern avoidance, proving structural equivalences, deriving exact enumerations for numerous classes, and revealing deep connections between permutation patterns, cycle structures, and classical integer sequences.