Wilf classification of bi-vincular permutation patterns

2009/10/27 by Robert Parviainen, Parviainen, Robert · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals #math.CO

paper · pdf · doi:10.48550/arxiv.0910.5103

Changed name of patterns to bi-vincular to confirm with new standard. Answered Question 2 and solved Conjecture 18. 16 pages, 4 figures

openalex publication_date 2009/10/27 · arxiv created 2009/11/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We classify all bi-vincular patterns of length two and three according to the number of permutations avoiding them. These patterns were recently defined by Bousquet-Melou et. al., and are natural generalizations of Babson and Steingrimsson's generalized patterns. The patterns are divided into seven and 24 Wilf classes, for lengths two and three, respectively. For most of the patterns an explicit form for the number of permutations avoiding the pattern is given.

Citations

• Generalized Pattern Avoidance
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Ascent sequences and upper triangular matrices containing non-negative integers

Cited by

• Counting general and self-dual interval orders

Related

• Some Wilf-equivalences for vincular patterns
• A New Class of Wilf-Equivalent Permutations
• Enumeration schemes for vincular patterns
• A Wilf equivalence related to two stack sortable permutations
• Enumerating permutations avoiding more than three Babson - Steingr'ımsson patterns