Asymptotic enumeration conjecture for deque-sortable and parallel two-stack-sortable permutations

For nZ0n\in\mathbb{Z}_{\geq0}, let pnp_n be the number of permutations of size nn sortable by two stacks in parallel, and let dnd_n be the number sortable by a deque. The generating functions DD and PP satisfy the equivalent relations stated in the preceding theorem.

Asymptotic enumeration conjecture. There exist constants μ\mu and γ\gamma such that

pnconstμnnγp_n\sim \operatorname{const}\cdot\mu^n\cdot n^\gamma

and

dnconstμnn3/2.d_n\sim \operatorname{const}\cdot\mu^n\cdot n^{-3/2}.

This conjecture is motivated by the relation between the generating functions for the two permutation classes. The paper presents it as a stronger conjecture whose proof is reduced to conjectures about the quarter-plane-loop generating function Q(a,u)Q(a,u); its resolution is not established here.

Sources & referencesView supporting material

Primary source

Andrew Elvey Price and Anthony J. Guttmann, “Permutations sortable by deques and by two stacks in parallel”, arXiv:1508.02273 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.