Some enumerative results related to ascent sequences

DOI10.1016/J.DISC.2013.10.006MaRDI QIDQ393161zbMATH OpenOpenAlexFDO

Authors Toufik Mansour, Mark Shattuck

Publication date 16 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationkernel methodNarayana numberascent sequence

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(24)

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

Describes a project that uses

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)