Journal of Integer Sequences, Vol. 22 (2019), Article 19.7.5

Consecutive Patterns in Inversion Sequences II: Avoiding Patterns of Relations


Juan S. Auli and Sergi Elizalde
Department of Mathematics
Dartmouth College
Hanover, NH 03755
USA

Abstract:

Inversion sequences are integer sequences e = e1 e2 ··· en such that 0 ≤ ei < i for each i. The study of patterns in inversion sequences was initiated by Corteel-Martinez-Savage-Weselcouch and Mansour-Shattuck in the classical (non-consecutive) case, and later by Auli-Elizalde in the consecutive case, where the entries of a pattern are required to occur in adjacent positions. In this paper we continue this investigation by considering consecutive patterns of relations, in analogy to the work of Martinez-Savage in the classical case. Specifically, given two binary relations R1, R2 ∈ {≤, ≥, <, >, =, ≠}, we study inversion sequences e with no subindex i such that ei R1 ei+1 R2 ei+2. By enumerating such inversion sequences according to their length, we obtain well-known quantities such as Catalan numbers, Fibonacci numbers and central polynomial numbers, relating inversion sequences to other combinatorial structures. We also classify consecutive patterns of relations into Wilf equivalence classes, according to the number of inversion sequences avoiding them, and into more restrictive classes that consider the positions of the occurrences of the patterns.

As a byproduct of our techniques, we obtain a simple bijective proof of a result of Baxter-Shattuck and Kasraoui about Wilf-equivalence of vincular patterns, and we prove a conjecture of Martinez and Savage, as well as related enumeration formulas for inversion sequences satisfying certain unimodality conditions.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A000027 A000045 A000071 A000079 A000085 A000108 A000124 A000325 A000522 A003422 A033321 A040000 A049774 A052169 A071356 A200403 A279561 A328357 A328358 A328429 A328430 A328431 A328432 A328433 A328434 A328435 A328436 A328437 A328438 A328439 A328440 A328441 A328442.)


Received June 17 2019; revised version received October 16 2019. Published in Journal of Integer Sequences, October 17 2019.


Return to Journal of Integer Sequences home page