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-\hat{I}{¼}_{3}t{)}^{\hat{I}}\pm \cdot {\log }^2(1-\hat{I}{¼}_{3}t),$$ so that $$[t^n]W(t)=w_n\sim \frac{c_0\hat{I}{¼}_3^n}{n^{(\hat{I}\pm +1)}\cdot {\log }^{\hat{I}}»n},$$ where $\hat{I}{¼}_3=9.69963634535(30),$ $\hat{I}\pm =2.0\pm \mathrm{0.25.}$ If $\hat{I}\pm =2$ exactly, then $\hat{I}»=-{\hat{I}}^2+1$, and we estimate ${\hat{I}}^2\approx -3.$ If $\hat{I}\pm$ is not an integer, then $\hat{I}»=-{\hat{I}}^2$, but we cannot give a useful estimate of ${\hat{I}}^2$. The growth constant estimate (just) contradicts a conjecture of the first author that $$9.702<\hat{I}{¼}_3\le \mathrm{9.704.}$$ We also prove a new rigorous lower bound of $\hat{I}{¼}_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.