10.46298/dmtcs.1323
https://dmtcs.episciences.org/1323
Corteel, Sylvie
Sylvie
Corteel
Martinez, Megan A.
Megan A.
Martinez
Savage, Carla D.
Carla D.
Savage
Weselcouch, Michael
Michael
Weselcouch
French National Research Agency (ANR)
ANR-08-JCJC-0011
Interactions Of Combinatorics
Patterns in Inversion Sequences I
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\"oder numbers, and Euler up/down numbers.
episciences.org
Mathematics - Combinatorics
05A05, 05A19
arXiv.org - Non-exclusive license to distribute
2023-02-06
2016-03-31
2016-03-31
eng
journal article
arXiv:1510.05434
10.48550/arXiv.1510.05434
1365-8050
https://dmtcs.episciences.org/1323/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
Vol. 18 no. 2, Permutation Patterns 2015
Permutation Patterns
Researchers
Students