Computational Approaches to Consecutive Pattern Avoidance in Permutations

Abstract

In recent years, there has been increasing interest in consecutive pattern avoidance in permutations. In this paper, we introduce two approaches to counting permutations that avoid a set of prescribed patterns consecutively. These algoritms have been implemented in the accompanying Maple package CAV, which can be downloaded from the author's website. As a byproduct of the first algorithm, we have a theorem giving a sufficient condition for when two pattern sets are strongly (consecutively) Wilf-Equivalent. For the implementation of the second algorithm, we define the cluster tail generating function and show that it always satisfies a certain functional equation. We also explain how the CAV package can be used to approximate asymptotic constants for single pattern avoidance.

12 pages

References in corpus (2)

• Anick-type resolutions and consecutive pattern avoidance
• Using homological duality in consecutive pattern avoidance

Cited by in corpus (5)

• Shuffle algebras, homology, and consecutive pattern avoidance
• Consecutive Patterns in Inversion Sequences
• On consecutive pattern-avoiding permutations of length 4, 5 and beyond
• Consecutive patterns in inversion sequences II: avoiding patterns of relations
• The 26 Wilf-equivalence classes of length five quasi-consecutive patterns