Permutations sortable by deques and by two stacks in parallel

DOI10.1016/J.EJC.2016.08.002zbMATH Open1348.05009DBLPjournals/ejc/Elvey-PriceG17arXiv1508.02273OpenAlexW2963958942WikidataQ67576010 ScholiaQ67576010MaRDI QIDQ326652FDOQ326652

Anthony J Guttmann, Andrew Elvey Price

Publication date: 12 October 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Recently Albert and Bousquet-M'elou cite{AB15} obtained the solution to the long-standing problem of the number of permutations sortable by two stacks in parallel (tsip). Their solution was expressed in terms of functional equations. We show that the equally long-standing problem of the number of permutations sortable by a double-ended queue (deque) can be simply related to the solution of the same functional equations. Subject to plausible, but unproved, conditions, the radius of convergence of both generating functions is the same. Numerical work confirms this conjecture to 10 significant digits. Further numerical work suggests that the coefficients of the deque generating function behave as $kapp{a}_{d}cdotm{u}^{n}cdot{n}^{-3/2},$ where $mu=8.281402207ldots,$ while the coefficients of the corresponding tsip generating function behave as $kapp{a}_{p}cdotm{u}^{n}cdot{n}^{gamma}$ with $gammaapprox-\mathrm{2.473.}$ The constants $kapp{a}_d$ and $kapp{a}_p$ are also estimated. {em Inter alia,} we study the asymptotics of quarter-plane loops, starting and ending at the origin, with weight $a$ given to north-west and east-south turns. The critical point varies continuously with $a,$ while the corresponding exponent variation is found to be continuous and monotonic for $a>-1/2,$ but discontinuous at $a=-1/2.$

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

Recommendations

• Permutations sortable by two stacks in parallel and quarter plane walks
• Permutations sortable by two stacks in parallel and quarter plane walks
• Permutations sortable by two stacks in series
• The enumeration of permutations sortable by pop stacks in parallel
• Asymptotics of 3-stack-sortable permutations

zbMATH Keywords

asymptotics of quarter-plane loops

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Sorting Using Networks of Queues and Stacks
• Permutations sortable by two stacks in series
• Permutations sortable by two stacks in parallel and quarter plane walks
• Permutations generated by stacks and deques

Cited In (8)

• Permutations sortable by two stacks in parallel and quarter plane walks
• 1324-avoiding permutations revisited
• Fighting fish and two-stack sortable permutations
• Asymptotics of 3-stack-sortable permutations
• Two permutation classes related to the bubble sort operator
• Permutations sortable by two stacks in series
• Sorting by shuffling methods and a queue
• Stack-sorting preimages of permutation classes

This page was built for publication: Permutations sortable by deques and by two stacks in parallel

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