Authors: Sylvie Corteel ; Megan A. Martinez ; Carla D. Savage ; Michael Weselcouch
NULL##NULL##NULL##NULL
Sylvie Corteel;Megan A. Martinez;Carla D. Savage;Michael Weselcouch
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,\ldots,e_n)$ is an inversion sequence if $0
\leq 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\ldots \pi_n$ by setting $e_i =
|\{j \ | \ j < i \ {\rm 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.
Cervetti, Matteo, 2022, A Generating Tree With A Single Label For Permutations Avoiding The Vincular Pattern 1â32â4, Pure Mathematics And Applications, 30, 1, pp. 56-62, 10.2478/puma-2022-0009.
Fu, Shishuo; Lin, Zhicong; Wang, Yaling, 2021, Refined Wilf-equivalences By Comtet Statistics, Electronic Research Archive, 29, 5, pp. 2877, 10.3934/era.2021018.
Lin, Zhicong; Kim, Dongsu, 2021, Refined Restricted Inversion Sequences, Annals Of Combinatorics, 25, 4, pp. 849-875, 10.1007/s00026-021-00550-7.