Journal of Integer Sequences, Vol. 21 (2018), Article 18.2.2

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

Megan Martinez
Department of Mathematics
Ithaca College
Ithaca, NY 14850 USA

Carla Savage
Department of Computer Science
North Carolina State University
Raleigh, NC 27695


Inversion sequences of length n, In, are integer sequences (e1, ... , en) with 0 ≤ ei < i 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 reframing the notion of a length-3 pattern from a word of length 3, w1 w2 w3, to a "triple of binary relations", (ρ1, ρ2, ρ3), and consider the set In1, ρ2, ρ3) consisting of those eIn with no i < j < k such that eiρ1ej, ejρ2ek, eiρ3ek. 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 a variety of classes of pattern avoiding permutations. For several combinatorial sequences, pattern avoiding inversion sequences provide a simpler interpretation than otherwise known.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000045 A000071 A000079 A000108 A000110 A000111 A000124 A000325 A000984 A001181 A001519 A004275 A005183 A006318 A009766 A033321 A034943 A047969 A047970 A049125 A071356 A088921 A090981 A091156 A098746 A106228 A108307 A108759 A113227 A117106 A124323 A166073 A175124 A200753 A212198 A229046 A263777 A263778 A263779 A263780 A279544 A279551 A279552 A279553 A279554 A279555 A279556 A279557 A279558 A279559 A279560 A279561 A279562 A279563 A279564 A279565 A279566 A279567 A279568 A279569 A279570 A279571 A279572 A279573.)

Received May 2 2017; revised version received January 5 2018; January 21 2018. Published in Journal of Integer Sequences, February 23 2018.

Return to Journal of Integer Sequences home page