Asymptotics of 3-stack-sortable permutations

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 $$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 \mathrm{0.25.}$ If $\alpha =2$ exactly, then $\lambda =-\beta +1$, and we estimate $\beta \approx -3.$ 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 that $$9.702<{\mu }_3\le \mathrm{9.704.}$$ We also prove a new rigorous lower bound of ${\mu }_3\ge 9.4854$, allowing us to disprove a conjecture of Bóna. 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.