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
USA
Abstract:
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 In(ρ1, ρ2, ρ3)
consisting of those e ∈ In
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