Shape-Wilf-equivalences for vincular patterns

Abstract

We extend the notion of shape-Wilf-equivalence to vincular patterns (also known as "generalized patterns" or "dashed patterns"). First we introduce a stronger equivalence on patterns which we call filling-shape-Wilf-equivalence. When vincular patterns $\alpha$ and $\beta$ are filling-shape-Wilf-equivalent, we prove that the direct sum $\alpha \oplus \sigma$ is filling-shape-Wilf-equivalent to $\beta \oplus \sigma$. We also discover two new pairs of patterns which are filling-shape-Wilf-equivalent: when $\alpha$, $\beta$, and $\sigma$ are nonempty consecutive patterns which are Wilf-equivalent, $\alpha \oplus \sigma$ is filling-shape-Wilf-equivalent to $\beta \oplus \sigma$; and for any consecutive pattern $\alpha$, $1\oplus \alpha$ is filling-shape-Wilf-equivalent to $1\ominus \alpha$. These equivalences generalize Wilf-equivalences found by Elizalde and Kitaev. These new equivalences imply many new Wilf-equivalences for vincular patterns

15 pages, 7 figures, 1 table. Presented at Permutation Patterns 2012; Accepted to Advanced in Applied Mathematics

References in corpus (2)

• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Shape-Wilf-equivalences for vincular patterns

Cited by in corpus (3)

• Shape-Wilf-equivalences for vincular patterns
• On avoidance of patterns of the form σ-τ by words over a finite alphabet
• The 26 Wilf-equivalence classes of length five quasi-consecutive patterns