Patterns in Inversion Sequences I

Abstract

Permutations that avoid given patterns have been studied in great depth for their connections to other fields of mathematics, computer science, and biology. From a combinatorial perspective, permutation patterns have served as a unifying interpretation that relates a vast array of combinatorial structures. In this paper, we introduce the notion of patterns in inversion sequences. A sequence $(e_1,e_2,\dots ,e_n)$ is an inversion sequence if $0\le e_i<i$ for all $i\in [n]$. Inversion sequences of length $n$ are in bijection with permutations of length $n$; an inversion sequence can be obtained from any permutation $\pi ={\pi }_1{\pi }_2\dots {\pi }_n$ by setting $e_i=|\{j|j<i\mathrm{and}{\pi }_j>{\pi }_i\}|$. This correspondence makes it a natural extension to study patterns in inversion sequences much in the same way that patterns have been studied in permutations. This paper, the first of two on patterns in inversion sequences, focuses on the enumeration of inversion sequences that avoid words of length three. Our results connect patterns in inversion sequences to a number of well-known numerical sequences including Fibonacci numbers, Bell numbers, Schröder numbers, and Euler up/down numbers.

References in corpus (1)

• A bijection to count (1-23-4)-avoiding permutations

Cited by in corpus (13)

• Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers
• An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences
• Refined restricted inversion sequences
• Consecutive Patterns in Inversion Sequences
• Length-Four Pattern Avoidance in Inversion Sequences
• On pattern avoidance in matchings and involutions
• Pattern Avoidance in Weak Ascent Sequences
• On $\underline{12}0$-avoiding inversion and ascent sequences
• Refined Wilf-equivalences by Comtet statistics
• Proofs of Conjectures about Pattern-Avoiding Linear Extensions
• Patterns in treeshelves
• Passing through a stack $k$ times with reversals
• Bijections for restricted inversion sequences and permutations with fixed points