Permutations sortable by two stacks in series

DOI10.1016/J.AAM.2016.09.003MaRDI QIDQ343835zbMATH OpenOpenAlexFDO

Authors Andrew Elvey Price, Anthony J Guttmann

Publication date 29 November 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationsstack sorting

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Data structures (68P05) Searching and sorting (68P10)

Abstract: We address the problem of the number of permutations that can be sorted by two stacks in series. We do this by first counting all such permutations of length less than 20 exactly, then using a numerical technique to obtain nineteen further coefficients approximately. Analysing these coefficients by a variety of methods we conclude that the OGF behaves as ${\displaystyle }$S(z) sim A (1 - mu cdot z)^gamma,${\displaystyle }$ where $mu=12.45pm0.15,$ $gamma=1.5pm0.3,$ and $Aapprox0.02$.

Recommendations

• Sorting with two ordered stacks in series.
• Permutations sortable by two stacks in parallel and quarter plane walks
• Permutations sortable by deques and by two stacks in parallel
• Permutations sortable by two stacks in parallel and quarter plane walks
• Two stacks in series: a decreasing stack followed by an increasing stack

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• 2-stack sorting is polynomial
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Permutations generated by a depth 2 stack and an infinite stack in series are algebraic
• Permutations generated by stacks and deques
• Permutations sortable by deques and by two stacks in parallel
• Permutations sortable by two stacks in parallel and quarter plane walks
• Series extension: predicting approximate series coefficients from a finite number of exact coefficients
• Sorting with two ordered stacks in series.

Cited in

(9)

• Permutations sortable by two stacks in parallel and quarter plane walks
• Permutations generated by a depth 2 stack and an infinite stack in series are algebraic
• Permutations sorted by a finite and an infinite stack in series
• 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 deques and by two stacks in parallel
• Permutations sortable by two stacks in parallel and quarter plane walks
• Sorting with two ordered stacks in series.

This page was built for publication: Permutations sortable by two stacks in series

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