Patterns in inversion sequences. I.

MaRDI QIDQ2831885zbMATH OpenFDO

Authors Megan A. Martinez, Carla D. Savage, Michael. Weselcouch, Sylvie Corteel

Publication date 3 November 2016

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.05434, https://dmtcs.episciences.org/1421/pdf

zbMATH Keywords

enumerationpattern avoidanceinversion sequencesSchröder numbers

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Abstract: 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 $0leq{e}_i<i$ for all $iin[n]$. Inversion sequences of length $n$ are in bijection with permutations of length $n$; an inversion sequence can be obtained from any permutation $pi=p{i}_{1}p{i}_{2}ldotsp{i}_n$ by setting $e_i=|j|j<imandp{i}_j>p{i}_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 well-known numerical sequences including Fibonacci numbers, Bell numbers, Schr"oder numbers, and Euler up/down numbers.

Recommendations

• Pattern avoidance in inversion sequences
• Inversion sequences avoiding pairs of patterns
• Inversion sequences avoiding a triple of patterns of 3 letters
• Consecutive patterns in inversion sequences
• Inversion sequences avoiding consecutive patterns

Cited in

(56)

• Inversion sequences avoiding a set of length-3 patterns
• Sorting inversion sequences
• Passing through a stack \(k\) times with reversals
• Consecutive patterns in inversion sequences. II: Avoiding patterns of relations
• Equivalence of the descents statistic on some (4,4)-avoidance classes of permutations
• Combinatorics of the symmetries of ascents in restricted inversion sequences
• Pattern-avoiding inversion sequences and open partition diagrams
• A proof of Lin's conjecture on inversion sequences avoiding patterns of relation triples
• On \(\underline{12} 0\)-avoiding inversion and ascent sequences
• Inversion sequences avoiding consecutive patterns
• Patterns of relation triples in inversion and ascent sequences
• Vincular patterns in inversion sequences
• Length-four pattern avoidance in inversion sequences
• Weak ascent sequences and related combinatorial structures
• Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers
• Enumeration of inversion sequences avoiding triples of relations
• Patterns in inversion sequences. II: Inversion sequences avoiding triples of relations
• Lattice points on polyominoes of inversion sequences
• The enumeration of inversion sequences avoiding the patterns 201 and 210
• A combinatorial bijection on di-sk trees
• A sextuple equidistribution arising in pattern avoidance
• Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions
• Pattern avoidance in inversion sequences
• Enumeration of smooth inversion sequences and proof of a recent related conjecture
• Inversion sequences avoiding 021 and another pattern of length four
• Inversion sequences avoiding {120,210} and another pattern of length three
• Inversion sequences avoiding pairs of patterns
• Bijections for restricted inversion sequences and permutations with fixed points
• On pattern avoidance in matchings and involutions
• Catalan words avoiding pairs of length three patterns
• Pattern avoidance in weak ascent sequences
• Inversion sequences and signed permutations
• Generating Trees for 0021-Avoiding Inversion Sequences and a Conjecture of Hong and Li
• Restricted inversion sequences and Schröder paths
• Bijections on pattern avoiding inversion sequences and related objects
• On 0012-avoiding inversion sequences and a conjecture of Lin and Ma
• Some \(\gamma \)-positive polynomials arising from enumerations of the pseudo Schröder paths
• Statistics on bargraphs of inversion sequences of permutations
• On -positive polynomials arising in pattern avoidance
• An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences
• Wilf equivalences between vincular patterns in inversion sequences
• Five classes of pattern avoiding inversion sequences under one roof: generating trees
• Inversion sequences avoiding a triple of patterns of 3 letters
• The \(\gamma \)-positive coefficients arising in segmented permutations
• Refined Wilf-equivalences by Comtet statistics
• Patterns in treeshelves
• Bijections for generalized Wilf equivalences
• Three classes of inversion sequences counted by large Schröder numbers
• Further enumeration results concerning a recent equivalence of restricted inversion sequences
• Counting inversion sequences by parity successions and runs
• Burstein’s permutation conjecture, Hong and Li’s inversion sequence conjecture and restricted Eulerian distributions
• Descent distribution on Catalan words avoiding ordered pairs of relations
• Inversion polynomials for permutations avoiding consecutive patterns
• Parameters in inversion sequences
• Three new refined Arnold families
• Inversion sequences avoiding quadruple length-3 patterns

This page was built for publication: Patterns in inversion sequences. I.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2831885)