Permutations avoiding a nonconsecutive instance of a 2- or 3-letter pattern

2006/10/13 by David Callan, Callan, David
Computer Science · Mathematics · #05A15 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A15 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0610428

Acknowledgment of priority

openalex publication_date 2006/10/13 · arxiv created 2006/11/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We count permutations avoiding a nonconsecutive instance of a two- or three-letter pattern, that is, the pattern may occur but only as consecutive entries in the permutation. Two-letter patterns give rise to the Fibonacci numbers. The counting sequences for the two representative three-letter patterns, 321 and 132, have respective generating functions (1+x²)(C(x)-1)/(1+x+x²-x C(x)) and C(x+x³) where C(x) is the generating function for the Catalan numbers.

Related

• From Fibonacci to Catalan permutations
• Pattern avoidance in circular permutations
• The 1-box pattern on pattern avoiding permutations
• Enumerating permutations avoiding a pair of Babson-Steingrimsson patterns
• Counting occurrences of a pattern of type (1,2) or (2,1) in permutations