Pattern-avoiding ascent sequences of length 3

DOI10.37236/11266MaRDI QIDQ2094900zbMATH OpenOpenAlexFDO

Authors Andrew R. Conway, Miles Conway, Andrew Elvey Price, Anthony J Guttmann

Publication date 8 November 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

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

dynamic programming algorithmgenerating function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Special sequences and polynomials (11B83) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Abstract: Pattern-avoiding ascent sequences have recently been related to set-partition problems and stack-sorting problems. While the generating functions for several length-3 pattern-avoiding ascent sequences are known, those avoiding 000, 100, 110, 120 are not known. We have generated extensive series expansions for these four cases, and analysed them in order to conjecture the asymptotic behaviour. We provide polynomial time algorithms for the 000 and 110 cases, and exponential time algorithms for the 100 and 120 cases. We also describe how the 000 polynomial time algorithm was detected somewhat mechanically given an exponential time algorithm. For 120-avoiding ascent sequences we find that the generating function has stretched-exponential behaviour and prove that the growth constant is the same as that for 201-avoiding ascent sequences, which is known. The other three generating functions have zero radius of convergence, which we also prove. For 000-avoiding ascent sequences we give what we believe to be the exact growth constant. We give the conjectured asymptotic behaviour for all four cases.

Review text

Summary: Pattern-avoiding ascent sequences have recently been related to set-partition problems and stack-sorting problems. While the generating functions for several length-3 pattern-avoiding ascent sequences are known, those avoiding 000, 100, 110, 120 are not known. We have generated extensive series expansions for these four cases, and analysed them in order to conjecture the asymptotic behaviour. We provide polynomial time algorithms for the \(000\) and \(110\) cases, and exponential time algorithms for the \(100\) and \(120\) cases. We also describe how the \(000\) polynomial time algorithm was detected somewhat mechanically given an exponential time algorithm. For 120-avoiding ascent sequences we find that the generating function has stretched-exponential behaviour and prove that the growth constant is the same as that for 201-avoiding ascent sequences, which is known. The other three generating functions have zero radius of convergence, which we also prove. For 000-avoiding ascent sequences we give what we believe to be the exact growth constant. We give the conjectured asymptotic behaviour for all four cases.

Recommendations

• Pattern avoidance in ascent sequences
• Some enumerative results related to ascent sequences
• Ascent sequences avoiding pairs of patterns
• On 021-avoiding ascent sequences
• Ascent sequences and 3-nonnesting set partitions

Cites work

• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Analysis of series expansions for non-algebraic singularities
• On partitions avoiding 3-crossings
• Pattern avoidance in ascent sequences
• Patterns in permutations and words.
• Series extension: predicting approximate series coefficients from a finite number of exact coefficients
• Transport of patterns by Burge transpose
• Vassiliev invariants and a strange identity related to the Dedekind eta-function

Cited in

(9)

• Weak ascent sequences and related combinatorial structures
• Ascent sequences avoiding pairs of patterns
• The first 330 terms of sequence A013583
• Difference ascent sequences
• Ascent sequences avoiding a triple of 3-letter patterns and Fibonacci numbers
• Pattern-avoiding Cayley permutations via combinatorial species
• Pattern-avoiding modified ascent sequences
• Self-modified difference ascent sequences
• Difference ascent sequences and related combinatorial structures

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Pattern-avoiding ascent sequences of length 3

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