Some enumerative results related to ascent sequences

DOI10.1016/J.DISC.2013.10.006zbMATH Open1278.05010arXiv1207.3755OpenAlexW2090855500MaRDI QIDQ393161FDOQ393161

Authors: Toufik Mansour, Mark Shattuck 

Publication date: 16 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: An ascent sequence is one consisting of non-negative integers in which the size of each letter is restricted by the number of ascents preceding it in the sequence. Ascent sequences have recently been shown to be related to (2+2)-free posets and a variety of other combinatorial structures. In this paper, we prove in the affirmative some recent conjectures concerning pattern avoidance for ascent sequences. Given a pattern $au$, let $mathcal{S}_{a}u(n)$ denote the set of ascent sequences of length $n$ avoiding $au$. Here, we show that the joint distribution of the statistic pair $(asc,zero)$ on $mathcal{S}_{0012}(n)$ is the same as $(asc,RLm)$ on the set of 132-avoiding permutations of length $n$. In particular, the ascent statistic on $mathcal{S}_{0012}(n)$ has the Narayana distribution. We also enumerate $S_{a}u(n)$ when $au=1012$ and $au=0123$ and confirm the conjectured formulas in these cases. We combine combinatorial and algebraic techniques to prove our results, in two cases, making use of the kernel method. Finally, we discuss the case of avoiding 210 and determine two related recurrences.

Full work available at URL: https://arxiv.org/abs/1207.3755

Recommendations

• On 021-avoiding ascent sequences
• Pattern avoidance in ascent sequences
• Ascent sequences avoiding pairs of patterns
• A new decomposition of ascent sequences and Euler-Stirling statistics
• Ascent sequences and 3-nonnesting set partitions

zbMATH Keywords

permutationkernel methodNarayana numberascent sequence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18)

Cites Work

• Title not available (Why is that?)
• Enumeration schemes and, more importantly, their automatic generation
• Pattern avoidance in set partitions.
• On pattern-avoiding partitions
• Generating functions for generating trees
• Patterns in permutations and words.
• Crossings and nestings of matchings and partitions
• On partitions avoiding 3-crossings
• A q-Analog of Restricted Growth Functions, Dobinski's Equality, and Charlier Polynomials
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Title not available (Why is that?)
• Enumerating \((2 + 2)\)-free posets by indistinguishable elements
• Ascent sequences and upper triangular matrices containing non-negative integers
• Ascent sequences and 3-nonnesting set partitions
• Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
• Pattern avoidance in ascent sequences

Cited In (24)

• Pattern avoidance in ascent sequences
• Patterns of relation triples in inversion and ascent sequences
• Vincular patterns in inversion sequences
• Generalized ballot sequences are ascent sequences
• Weak ascent sequences and related combinatorial structures
• Ascent sequences avoiding pairs of patterns
• A new decomposition of ascent sequences and Euler-Stirling statistics
• An operator on ascent sequences
• Ascent sequences and the binomial convolution of Catalan numbers
• Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions
• Restricted ascent sequences and Catalan numbers
• Modified ascent sequences and Bell numbers
• Difference ascent sequences
• Last symbol distribution in pattern avoiding Catalan words
• Ascent sequences and 3-nonnesting set partitions
• Ascent sequences avoiding a triple of 3-letter patterns and Fibonacci numbers
• On 021-avoiding ascent sequences
• Title not available (Why is that?)
• Efficient generation of restricted growth words
• Ascent sequences and Fibonacci numbers
• Bi-symmetric multiple equidistributions on ascent sequences
• Catalan pairs and Fishburn triples
• Pattern-avoiding ascent sequences of length 3
• Transport of patterns by Burge transpose

Uses Software

• OEIS
• WILF
• HERB

This page was built for publication: Some enumerative results related to ascent sequences

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