Inversion sequences avoiding a pair of patterns of type $(2,1)$

An inversion sequence of length $n$ is a sequence of integers $e = e_0 \dotsm e_n$ which satisfies $0 \leq e_i \leq i$, for all $i = 0, 1, \dotsc , n$. We say that $e$ avoids a pattern $ab\textrm{-}c$ of type $(2, 1)$ if does not exist $i, j$ such that $0 \leq i \lt j −1 \leq n-1$ and the subsequence $\pi_i, \pi_{i+1}, \pi_j$ has the same order isomorphic as abc. For a set of patterns $B$, let $\mathbf{I}_n (B)$ be the set of inversion sequences of length n that avoid all the patterns from $B$. We say that two sets of patterns $B$ and $C$ are I‑Wilf equivalent if ${\lvert \mathbf{I}_n (B) \rvert} = {\lvert \mathbf{I}_n (C) \rvert}$, for all $n \geq 0$. In this paper, we show that the number of I‑Wilf equivalences among pairs of patterns of type $(2, 1)$ is $72$. In particular, we present connections to Bell numbers, ascent sequences, and permutations avoiding length-$4$ vincular pattern.

Keywords

inversion sequences, generating trees, Kernel method, pattern avoidance, ascent sequences

2010 Mathematics Subject Classification

Primary 05A05. Secondary 05A15.

Full Text (PDF format)

Received 3 January 2023

Accepted 19 March 2023

Published 23 January 2024