Emerging Consecutive Pattern Avoidance

Basic Information

• Paper ID: 2511.02442
• Title: Emerging consecutive pattern avoidance
• Authors: Nathanaël Hassler, Sergey Kirgizov (Université Bourgogne Europe)
• Classification: math.CO (Combinatorics), cs.DM (Discrete Mathematics)
• Publication Date: November 5, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.02442

Abstract

This paper investigates the asymptotic popularity problem: finding the limiting probability of discovering a given consecutive pattern at a random position in a random permutation from one of 18 permutation classes that avoid at least two consecutive patterns of length 3. The study demonstrates that for 10 classes, this popularity can be directly derived from the permutation structure. By combining analytic and bijective methods, the authors provide detailed analysis of two more complex cases. The problem remains open for 5 classes.

Research Background and Motivation

Research Problem

This paper studies the asymptotic behavior of consecutive pattern avoidance in permutations. Specifically:

• Given permutation classes avoiding certain consecutive patterns of length 3
• Study the asymptotic popularity of other unavoided patterns in these classes
• Asymptotic popularity is defined as: the limit as n → ∞ of the probability of finding a specific pattern p at a random position in a random permutation of size n

Problem Significance

1. Theoretical Importance: Reveals a "fascinating fact"—certain patterns asymptotically disappear (probability approaches 0)
2. Extension of Classical Results: Extends work by Bóna and Homberger on classical (non-consecutive) patterns to consecutive patterns
3. Connection of Combinatorial Objects: Establishes bijections between permutations and other combinatorial structures (e.g., Dyck paths, involutions)

Limitations of Existing Methods

• Bóna and Homberger's work applies only to classical (non-consecutive) patterns
• Kitaev and Mansour provided enumeration of 18 avoidance classes but did not study asymptotic popularity
• Lack of systematic methods for handling all 18 permutation classes

Research Motivation

Stems from work by Baril, Burstein, and Kirgizov on Class 7, where they used bijections between permutations and scattered Dyck paths to transfer patterns, inspiring the present work.

Core Contributions

1. Systematic Study of 18 Classes: Complete analysis of the 18 permutation classes avoiding at least two consecutive patterns of length 3 proposed by Kitaev-Mansour
2. Resolution of 10 Simple Classes: For 10 permutation classes (Classes 1,2,3,5,6,8,9,16,18 and the previously resolved Class 7), asymptotic popularity is derived directly from structure
3. In-Depth Analysis of 2 Complex Classes:
   • Class 11 (Av(123,132,321)): Combines analytic and combinatorial methods
   • Class 17 (Av(123,132)): Employs Foata transformation and involution bijections
4. Identification of Open Problems: Clearly identifies 5 permutation classes (Classes 10,12,13,14,15) where the problem remains open
5. Discovery of Pattern Disappearance: Proves that in certain classes, specific patterns have asymptotic popularity of 0 (pattern disappearance)

Detailed Methodology

Task Definition

Input:

• Permutation class $A_n = \text{Av}_n(p_1, \ldots, p_m)$ avoiding consecutive patterns $p_1, \ldots, p_m$
• Unavoided consecutive pattern p of length 3

Output:

• Asymptotic popularity $\text{pop}_A(p) := \lim_{n \to \infty} \frac{p_n^A}{n|A_n|}$

where $p_n^A$ is the total number of occurrences of pattern p across all permutations in $A_n$.

Core Concepts

Consecutive Pattern: A permutation π contains consecutive pattern p if there exists a consecutive subsequence $a_i a_{i+1} \cdots a_{i+r-1}$ that is order-isomorphic to p.

Symmetry Operations:

• Reversal R(π): reverse the permutation
• Complement C(π): replace each element a with n+1-a
• These operations preserve consecutive pattern occurrences

Method Classification

1. Structural Analysis Method (Simple Classes)

For permutation classes with simple structure, popularity is derived directly from the form:

Class 1 (Av(123,132,312,321)):

• Contains only 2 alternating permutations
• Symmetry directly gives pop(213) = pop(231) = 1/2

Class 18 (Av(132,231)):

• Permutation form: $a_1 \cdots a_k 1 b_1 \cdots b_{n-k-1}$
• where $a_1 \cdots a_k$ is decreasing, $b_1 \cdots b_{n-k-1}$ is increasing
• Count: occurrences of 321 = $\sum_{k=1}^{n-1} \binom{n-1}{k}(k-1) = (n-1) \cdot 2^{n-2} - 2^{n-1} + 1$
• Conclusion: pop₁₈(321) = pop₁₈(123) = 1/2, pop₁₈(213) = pop₁₈(312) = 0

Class 16 (Av(123,321)):

• Uses symmetry: class is stable under R, C, R∘C
• Four unavoided patterns correspond one-to-one via these bijections
• Conclusion: pop₁₆(132) = pop₁₆(231) = pop₁₆(312) = pop₁₆(213) = 1/4

2. Analytic Method (Class 11)

Class 11 (Av(123,132,321)):

Step 1: Structural Analysis

• Permutations are alternating or reverse alternating
• Reading right-to-left skipping one element yields an increasing sequence
• Divided into two subsets: $A_n^r$ (last element is 1) and $A_n^l$ (second-to-last element is 1)
• $|A_n^r| = (n-2)!!$, $|A_n^l| = (n-1)!!$

Step 2: Pattern 231 Counting Direct observation of positional structure: $231_n = (n-1)!! \left\lceil \frac{n-3}{2} \right\rceil + (n-2)!! \left\lceil \frac{n-2}{2} \right\rceil$

Step 3: Pattern 312 Recurrence Establish recurrence relation (Lemma 3.2):

• $312_n^r = 312_{n-1}^l$
• $312_n^l = (n-1)(312_{n-2}^l + (n-3)!!) - (n-5)!! \frac{(n-3)(n-2)}{2}$

Step 4: Generating Function Solution Set $u_n := \frac{312_n^l}{(n-1)!!}$, obtaining generating function: $f(z) = \frac{z(2(z-1)\ln(1-z) + z^3 + 3z^2 - 2z)}{4(1-z)^2(1+z)}$

Conclusion: $312_n^l = (n-1)!! \left( \frac{(-1)^{n-1} + n - 3}{4} + \frac{1}{2} \sum_{\substack{k=1\\k \neq n \bmod 2}}^{n-1} \frac{1}{k} \right)$

Asymptotic results: pop₁₁(231) = 1/2, pop₁₁(213) = pop₁₁(312) = 1/4

3. Bijective Method (Class 17)

Class 17 (Av(123,132)):

Core Tool: Foata Transformation Claesson proved the Foata transformation establishes a bijection between Av_n(123,132) and the set of involutions I_n.

Standard Form:

1. Each cycle begins with its minimum element
2. Cycles are ordered by minimum element in decreasing order
3. Removing parentheses yields the permutation

Pattern Correspondence (Table 2):

• 321 in Av(123,132) ↔ (c)(b)(a) or forms with fixed points in I_n
• 231 ↔ (bc)(a⋆) (no fixed points)
• 213 ↔ (⋆b)(ac) (no fixed points)
• 312 ↔ (⋆c)(ab) (no fixed points)

Key Lemmas:

• Lemma 4.2: Asymptotic behavior of fixed point count $\frac{\text{fp}_n}{|I_n|} \sim_{n \to \infty} \sqrt{n}$ This shows fixed points are sparse in involutions, making forms with fixed points negligible.
• Lemma 4.3: Only need to compute popularity of fixed-point-free patterns

Pattern 231 Analysis (Proposition 4.4):

• Pattern α = (bc)(a⋆) corresponds to two consecutive transpositions
• Each pair of consecutive transpositions produces exactly one α and one β or γ
• Conclusion: pop₁₇(231) = 1/2, pop₁₇(321) = 0

Pattern 213 Analysis (Most Complex):

• Corresponds to pattern 2314 in Av(123,132)
• Establish recurrence relation (Lemma 4.5): $2314_n = 2314_{n-1} + (n-1) \cdot 2314_{n-2} + \binom{n-2}{2}|I_{n-4}|$
• Exponential generating function (Proposition 4.6): $G(z) = \frac{e^{\frac{(1+z)^2}{2}}}{2} \int_0^z e^{-\frac{(1+t)^2}{2}} dt + \frac{z(z-2)e^{z+\frac{z^2}{2}}}{4}$
• Asymptotic Analysis:
  • First term: $[z^n]z(z-2)e^{z+\frac{z^2}{2}} \sim \frac{n|I_n|}{n!}$
  • Second term: Using saddle point method proves $[z^n]F(z) = o(\frac{n|I_n|}{n!})$
  • Choose saddle point $\zeta = \sqrt{n}$ to obtain sufficient bounds

Conclusion: pop₁₇(312) = pop₁₇(213) = 1/4

Technical Innovations

1. Hybrid Approach: First systematic combination of structural analysis, generating functions, and bijective methods for studying asymptotic consecutive pattern popularity
2. Novel Saddle Point Application: In Class 17, simplifies analysis by choosing approximate saddle point $\zeta = \sqrt{n}$ rather than exact saddle point
3. Pattern Transfer: Uses Foata transformation to convert pattern problems in permutations to cycle structure problems in involutions
4. Fixed Point Sparsity: Proves $O(\sqrt{n})$ growth rate of fixed points makes them negligible in asymptotic analysis

Experimental Setup

Data Sources

This is a purely theoretical work based primarily on:

• Enumeration results for 18 classes by Kitaev and Mansour
• Known generating functions and asymptotic formulas

Verification Methods

Although lacking traditional experiments, the authors mention:

• Numerical experiments on Classes 10,12,13,14,15
• Very slow convergence rates, making reliable conjectures difficult

Experimental Results

Main Results (Summarized in Table 1)

Key Findings

1. Pattern Disappearance Phenomenon:
   • In multiple classes, certain patterns have asymptotic popularity 0 (e.g., 231 in Class 2, 321 in Class 17)
   • Described as a "rather fascinating fact"
2. Symmetry Results:
   • Class 16 exhibits perfect four-fold symmetry (all four patterns have popularity 1/4)
   • Many classes show 1/2 symmetric distribution
3. Rational Popularity:
   • All resolved cases have rational popularity (0, 1/4, 1/2, 1)
   • Open question: Do irrational popularities exist?

Related Work

Classical Pattern Avoidance

• Bóna & Homberger 1,2,3: Study permutation classes avoiding one length-3 classical pattern
  • Prove asymptotic popularity of 321 in Av(123) and Av(132) is 1
• Janson 15,16: Study limiting distributions of length-3 classical patterns in Av(132) and Av(321)

Consecutive Pattern Research

• Kitaev & Mansour 17,18,19: Provide enumeration of 18 avoidance classes (foundation of this work)
• Elizalde & Noy 9,10:
  • Methods based on increasing trees and box products
  • Adaptations of Goulden-Jackson cluster method

Bijections and Pattern Transfer

• Barnabei, Bonetti, Silimbani 5:
  • Study joint distribution of size-3 consecutive patterns in Av(312)
  • Use Krattenthaler bijections and Deutsch involutions
• Baril, Burstein, Kirgizov 4:
  • Study faro words and pattern statistics in permutations
  • Direct predecessor and motivation for this work

Asymptotic Normality

• Borga 6: Study asymptotic normality of consecutive pattern occurrences in permutations avoiding certain patterns using generating trees

Conclusions and Discussion

Main Conclusions

1. Completeness: Systematically resolves 13 of 18 classes (10 simple + 2 complex + 1 prior)
2. Methodology: Demonstrates effective combination of structural analysis, generating functions, and bijective methods
3. Theoretical Insights: Reveals interesting phenomena including pattern disappearance and symmetries

Limitations

1. Incomplete Work: 5 permutation classes (Classes 10,12,13,14,15) remain open
2. Numerical Difficulties: These open classes have very slow convergence, making numerical conjecture formation difficult
3. Method Limitations: Existing methods appear insufficient for the remaining complex cases

Future Directions

The authors propose several open problems in Section 5:

1. Conjecture 5.1: If popₐ(p) = 0, then for subclasses B avoiding p, popB(q) = popₐ(q)
   • Holds in all resolved cases
2. Extended Problems:
   • What happens when avoiding only one consecutive pattern of length 3?
   • Can we find pattern sets producing irrational asymptotic popularities?
   • Does limit (1.1) always exist? How to characterize existence?
3. Methodological Questions:
   • How to resolve remaining 5 classes using enumeration or probabilistic methods?
   • Does a unified framework exist for handling all cases?

In-Depth Evaluation

Strengths

1. Strong Systematicity:
   • First systematic study of asymptotic popularity for 18 permutation classes
   • Clear classification and methodology (simple vs. complex)
2. Methodological Diversity:
   • Flexible application of structural analysis, generating functions, bijections, saddle point methods
   • Class 17 analysis particularly elegant, demonstrating organic combination of multiple techniques
3. Theoretical Depth:
   • Lemma 4.2 on fixed point sparsity is elegant
   • Generating function derivations are rigorous (especially Class 11's differential equations)
4. Clear Presentation:
   • Well-structured progression from simple to complex
   • Table 1 provides clear overview
   • Figures 1-2 aid understanding

Weaknesses

1. Incompleteness:
   • 5 classes unresolved (28% of total)
   • No deep analysis or partial results for difficult cases
2. Limited Numerical Support:
   • Numerical experiments mentioned but no concrete data shown
   • Lack of quantitative convergence rate analysis
3. Conjecture Verification:
   • Conjecture 5.1 verified only on resolved cases, lacking broader evidence
4. Technical Details:
   • Saddle point choice $\zeta = \sqrt{n}$ in Class 17 could be better motivated
   • Some computational steps have larger jumps

Impact

1. Theoretical Contribution:
   • Initiates systematic study of asymptotic consecutive pattern popularity
   • Provides new perspective for pattern avoidance theory
2. Methodological Value:
   • Demonstrates effective combination of multiple techniques
   • Pattern transfer ideas applicable to other combinatorial structures
3. Inspirational Value:
   • Clearly stated, interesting open problems
   • Likely to inspire new research directions
4. Limitations:
   • Primarily theoretical results with unclear practical applications
   • Difficulty of remaining problems may limit near-term impact

Applicable Domains

1. Combinatorics Research:
   • Permutation pattern theory
   • Asymptotic enumeration
   • Generating function methods
2. Algorithm Design:
   • Restricted permutation generation
   • Pattern matching algorithms
3. Related Fields:
   • Possible applications to constrained models in statistical physics
   • Connections to pattern avoidance problems in genomics

References

Key references:

1. 4 Baril, Burstein, Kirgizov (2021): Direct motivation for this work
2. 17 Kitaev (2003): Enumeration foundation for 18 classes
3. 7 Claesson (2001): Foata transformation bijection (key to Class 17)
4. 1-3 Bóna & Homberger (2010-2012): Pioneering work on classical patterns
5. 11 Flajolet & Sedgewick (2005): Standard reference for analytic combinatorics

Overall Assessment: This is a solid combinatorics paper that systematically investigates a natural and interesting problem. Methodologically, it demonstrates effective combination of multiple techniques, with particularly sophisticated analysis of Classes 11 and 17 reflecting deep technical expertise. While 5 classes remain unresolved, the completed work establishes a solid foundation for the field. The paper is clearly written with interesting results (particularly the pattern disappearance phenomenon) and well-formulated open problems. For researchers in combinatorics, especially permutation pattern theory, this is a paper well worth careful study.