Asymptotics of 3-stack-sortable permutations

DOI10.37236/10134MaRDI QIDQ2034079zbMATH OpenOpenAlexFDO

Authors Colin Defant, Andrew Elvey Price, Anthony J Guttmann

Publication date 21 June 2021

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/2009.10439

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

permutation patternpolynomial-time algorithmstack-sorting

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Abstract: We derive a simple functional equation with two catalytic variables characterising the generating function of 3-stack-sortable permutations. Using this functional equation, we extend the 174-term series to 1000 terms. From this series, we conjecture that the generating function behaves as ${\displaystyle }$W(t) sim C_0(1-mu_3 t)^alpha cdot log^�eta(1-mu_3 t), ${\displaystyle }$ so that ${\displaystyle }$[t^n]W(t)=w_n sim frac{c_0mu_3^n}{ n^{(alpha+1)}cdot log^lambda{n}} ,${\displaystyle }$ where $m{u}_3=9.69963634535(30),$ $alpha=2.0pm\mathrm{0.25.}$ If $alpha=2$ exactly, then $$, and we estimate $$ If $alpha$ is not an integer, then $$, but we cannot give a useful estimate of $$. The growth constant estimate (just) contradicts a conjecture of the first author that ${\displaystyle }$9.702 < mu_3 le 9.704.${\displaystyle }$ We also prove a new rigorous lower bound of $m{u}_{3}geq9.4854$, allowing us to disprove a conjecture of B'ona. We then further extend the series using differential-approximants to obtain approximate coefficients $O(t^{2000}),$ expected to be accurate to $20$ significant digits, and use the approximate coefficients to provide additional evidence supporting the results obtained from the exact coefficients.

Review text

Summary: We derive a simple functional equation with two catalytic variables characterising the generating function of 3-stack-sortable permutations. Using this functional equation, we extend the 174-term series to 1000 terms. From this series, we conjecture that the generating function behaves as \[W(t) \sim C_0(1-\mu_3 t)^\alpha \cdot \log^\beta(1-\mu_3 t),\] so that \[[t^n]W(t)=w_n \sim \frac{c_0\mu_3^n}{ n^{(\alpha+1)}\cdot \log^\lambda{n}} ,\] where \(\mu_3 = 9.69963634535(30), \alpha = 2.0 \pm 0.25.\) If \(\alpha = 2\) exactly, then \(\lambda = -\beta+1\), and we estimate \(\beta \approx -2,\) but with a wide uncertainty of \(\pm 1.\) If \(\alpha\) is not an integer, then \(\lambda=-\beta \), but we cannot give a useful estimate of \(\beta \). The growth constant estimate (just) contradicts a conjecture of the first author [J. Comb. Theory, Ser. A 172, Article ID 105209, 26 p. (2020; Zbl 1433.05005)] that \[9.702 < \mu_3 \leqslant 9.704.\] We also prove a new rigorous lower bound of \(\mu_3\geqslant 9.4854\), allowing us to disprove a conjecture of \textit{M. Bóna} [Electron. J. Comb. 9, No. 2, Research paper A1, 16 p. (2003; Zbl 1028.05003); Combinatorics of permutations. 2nd ed. Boca Raton, FL: CRC Press (2012; Zbl 1255.05001)]. We then further extend the series using differential-approximants to obtain approximate coefficients \(O(t^{2000}),\) expected to be accurate to 20 significant digits, and use the approximate coefficients to provide additional evidence supporting the results obtained from the exact coefficients.

Recommendations

• Counting 3-stack-sortable permutations
• Stack-sortable permutations and beyond
• Multi-static enumeration of two-stack sortable permutations
• Permutations sortable by two stacks in series
• Permutations sortable by deques and by two stacks in parallel

Cites work

• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• A survey of stack-sorting disciplines
• Analytic combinatorics
• Combinatorics of permutations
• Counting 3-stack-sortable permutations
• Counting coloured planar maps: differential equations
• Counting planar Eulerian orientations
• Counting quadrant walks via Tutte's invariant method (extended abstract)
• Describing West-3-stack-sortable permutations with permutation patterns
• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Modern computer algebra
• On the nature of the generating series of walks in the quarter plane
• Permutations sortable by deques and by two stacks in parallel
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• Preimages under the stack-sorting algorithm
• Series extension: predicting approximate series coefficients from a finite number of exact coefficients
• Walks with small steps in the quarter plane

Cited in

(8)

• Meeting covered elements in -Tamari lattices
• Counting 3-stack-sortable permutations
• Stack-sortable permutations and beyond
• Permutations sortable by deques and by two stacks in parallel
• Pop-stack-sorting for Coxeter groups
• Fertilitopes
• Highly sorted permutations with respect to a 312-avoiding stack
• Descent generating polynomials for (n - 3)- and (n - 4)-stack-sortable (pattern-avoiding) permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Asymptotics of 3-stack-sortable permutations

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