Enumeration schemes for vincular patterns

2011/08/12 by Andrew M. Baxter, Lara Pudwell, Baxter, Andrew M. +1 · 1 citation
Mathematics · #05A05 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1108.2642

openalex publication_date 2011/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We extend the notion of an enumeration scheme developed by Zeilberger and Vatter to the case of vincular patterns (also called "generalized patterns" or "dashed patterns"). In particular we provide an algorithm which takes in as input a set B of vincular patterns and search parameters and returns a recurrence (called a "scheme") to compute the number of permutations of length n avoiding B or confirmation that no such scheme exists within the search parameters. We also prove that if B contains only consecutive patterns and patterns of the form σ₁σ₂ ... σ_t-1-σ_t, then such a scheme must exist and provide the relevant search parameters. The algorithms are implemented in Maple and we provide empirical data on the number of small pattern sets admitting schemes. We make several conjectures on Wilf-classification based on this data. We also outline how to refine schemes to compute the number of B-avoiding permutations of length n with k inversions.

Citations

• Generalized Pattern Avoidance

Cited by

• The insertion encoding of restricted growth functions

Related

• Approaches for enumerating permutations with a prescribed number of occurrences of patterns
• Some Wilf-equivalences for vincular patterns
• Refining enumeration schemes to count according to permutation statistics
• Wilf classification of bi-vincular permutation patterns
• The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns