Permutations sortable by two stacks in series

DOI10.1016/J.AAM.2016.09.003zbMATH Open1351.05008arXiv1510.08663OpenAlexW2962822399MaRDI QIDQ343835FDOQ343835

Authors: Andrew Elvey Price, Anthony J Guttmann 

Publication date: 29 November 2016

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

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$.

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

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

zbMATH Keywords

permutationsstack sorting

Mathematics Subject Classification ID

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

Cites Work

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

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)