Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations

Abstract

Inversion sequences of length $n$, ${\mathbf{I}}_n$, are integer sequences $(e_1,\dots ,e_n)$ with $0\le e_i<n$ for each $i$. The study of patterns in inversion sequences was initiated recently by Mansour-Shattuck and Corteel-Martinez-Savage-Weselcouch through a systematic study of inversion sequences avoiding words of length 3. We continue this investigation by generalizing the notion of a pattern to a fixed triple of binary relations $({\rho }_1,{\rho }_2,{\rho }_3)$ and consider the set ${\mathbf{I}}_n({\rho }_1,{\rho }_2,{\rho }_3)$ consisting of those $e\in {\mathbf{I}}_n$ with no $i<j<k$ such that $e_i{\rho }_1{e}_j$, $e_j{\rho }_2{e}_k$, and $e_i{\rho }_3{e}_k$. We show that "avoiding a triple of relations" can characterize inversion sequences with a variety of monotonicity or unimodality conditions, or with multiplicity constraints on the elements. We uncover several interesting enumeration results and relate pattern avoiding inversion sequences to familiar combinatorial families. We highlight open questions about the relationship between pattern avoiding inversion sequences and families such as plane permutations and Baxter permutations. For several combinatorial sequences, pattern avoiding inversion sequences provide a simpler interpretation than otherwise known.

Cited by in corpus (11)

• Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers
• Cauchy-Stieltjes families with polynomial variance functions and generalized orthogonality
• Inversion sequences avoiding pairs of patterns
• 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 $\underline{12}0$-avoiding inversion and ascent sequences
• Consecutive patterns in inversion sequences II: avoiding patterns of relations
• Proofs of Conjectures about Pattern-Avoiding Linear Extensions
• Bijections for restricted inversion sequences and permutations with fixed points