episciences.org_1323_1675649836
1675649836
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
03
31
2016
Vol. 18 no. 2, Permutation...
Permutation Patterns
Patterns in Inversion Sequences I
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 wellknown numerical sequences including
Fibonacci numbers, Bell numbers, Schr\"oder numbers, and Euler up/down numbers.
03
31
2016
1323
French National Research Agency (ANR)
ANR08JCJC0011
https://arxiv.org/licenses/nonexclusivedistrib/1.0
arXiv:1510.05434
10.48550/arXiv.1510.05434
https://arxiv.org/abs/1510.05434v3
https://arxiv.org/abs/1510.05434v1
10.46298/dmtcs.1323
https://dmtcs.episciences.org/1323

https://dmtcs.episciences.org/1421/pdf

https://dmtcs.episciences.org/1421/pdf