Ascent sequences avoiding pairs of patterns

MaRDI QIDQ2260633zbMATH OpenFDO

Authors Andrew M. Baxter, Lara Pudwell

Publication date 11 March 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.4100, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p58

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

ascent sequencesDyck pathsgenerating treespattern avoidance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Combinatorial identities, bijective combinatorics (05A19) Trees (05C05)

Abstract: Ascent sequences were introduced by Bousquet-Melou et al. in connection with (2+2)-avoiding posets and their pattern avoidance properties were first considered by Duncan and Steingrimsson. In this paper, we consider ascent sequences of length $n$ avoiding two patterns of length 3, and we determine an exact enumeration for 16 different pairs of patterns. Methods include simple recurrences, bijections to other combinatorial objects (including Dyck paths and pattern-avoiding permutations), and generating trees. We also provide an analogue of the Erdos-Szekeres Theorem to prove that any sufficiently long ascent sequence contains either many copies of the same number or a long increasing subsequence, with a precise bound.

Review text

Summary: Ascent sequences were introduced by \textit{M. Bousquet-Melou} et al. [J. Comb. Theory, Ser. A 117, No. 7, 884--909 (2010; Zbl 1225.05026)] in connection with \((2+2)\)-avoiding posets and their pattern avoidance properties were first considered by \textit{P. Duncan} and \textit{E. Steingrímsson} [Electron. J. Comb. 18, No. 1, Research Paper P226, 17 p. (2011; Zbl 1243.05010)]. In this paper, we consider ascent sequences of length \(n\) avoiding two patterns of length 3, and we determine an exact enumeration for 16 different pairs of patterns. Methods include simple recurrences, bijections to other combinatorial objects (including Dyck paths and pattern-avoiding permutations), and generating trees. We also provide an analogue of the Erdős-Szekeres theorem to prove that any sufficiently long ascent sequence contains either many copies of the same number or a long increasing subsequence, with a precise bound.

Recommendations

• Pattern avoidance in ascent sequences
• Pattern-avoiding ascent sequences of length 3
• Inversion sequences avoiding pairs of patterns
• On 021-avoiding ascent sequences
• Pattern avoidance in inversion sequences
• Avoiding consecutive patterns in permutations
• Inversion sequences avoiding consecutive patterns
• Some enumerative results related to ascent sequences
• Consecutive patterns in inversion sequences. II: Avoiding patterns of relations
• Avoidance of classical patterns by Catalan sequences

Cites work

• $n!$ matchings, $n!$ posets
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Ascent sequences and Fibonacci numbers
• Ascent sequences and upper triangular matrices containing non-negative integers
• Counting strings in Dyck paths
• Directed column-convex polyominoes by recurrence relations
• Enumerating \((2 + 2)\)-free posets by indistinguishable elements
• Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
• Finitely labeled generating trees and restricted permutations
• Free rises, restricted partitions, and \(q\)-Fibonacci polynomials
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• Nondecreasing Dyck paths and \(q\)-Fibonacci numbers
• On 021-avoiding ascent sequences
• On multiple pattern avoiding set partitions
• Pattern avoidance in ascent sequences
• Patterns in permutations and words.
• Restricted ascent sequences and Catalan numbers
• Restricted partitions and generalized Catalan numbers
• Some enumerative results related to ascent sequences

Cited in

(25)

• On 021-avoiding ascent sequences
• Pattern-avoiding ascent sequences of length 3
• Transport of patterns by Burge transpose
• Weak ascent sequences and related combinatorial structures
• On \(\underline{12} 0\)-avoiding inversion and ascent sequences
• Patterns of relation triples in inversion and ascent sequences
• Vincular patterns in inversion sequences
• A note on \(p\)-ascent sequences
• Ascent sequences and 3-nonnesting set partitions
• Ascent sequences and the binomial convolution of Catalan numbers
• Generalized ballot sequences are ascent sequences
• Inversion sequences avoiding pairs of patterns
• Some enumerative results related to ascent sequences
• scientific article; zbMATH DE number 861399 (Why is no real title available?)
• Catalan words avoiding pairs of length three patterns
• Ascent sequences and Fibonacci numbers
• Weighted sums of Fibonacci and Lucas numbers through colorful tilings
• Pattern avoidance in weak ascent sequences
• Ascent sequences avoiding a triple of 3-letter patterns and Fibonacci numbers
• Pattern avoidance in ascent sequences
• Ascent sequences and weak ascent sequences avoiding a quadruple of length-3 patterns
• Self-modified difference ascent sequences
• Ascent sequences avoiding a triple of length-3 patterns
• Two combinatorial interpretations of rascal numbers
• On ascent sequences avoiding 021 and a pattern of length four

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Ascent sequences avoiding pairs of patterns

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