Sorting twice through a stack

DOI10.1016/0304-3975(93)90321-JzbMath0797.68041OpenAlexW2006800405WikidataQ60638479 ScholiaQ60638479MaRDI QIDQ688711

Julian West

Publication date: 19 October 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90321-j

zbMATH Keywords

Catalan numberpermutation sortingstack-sorting

Mathematics Subject Classification ID

Searching and sorting (68P10) Factorials, binomial coefficients, combinatorial functions (05A10) Combinatorics in computer science (68R05)

Related Items

2-stack sorting is polynomial ⋮ 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers ⋮ Fighting fish and two-stack sortable permutations ⋮ Permutations with forbidden subsequences and nonseparable planar maps ⋮ Sorting Cayley permutations with pattern-avoiding machines ⋮ \(k\)-pop stack sortable permutations and \(2\)-avoidance ⋮ Sorting with networks of data structures ⋮ Stack words, standard tableaux and Baxter permutations ⋮ Lattice paths and \((n - 2)\)-stack sortable permutations ⋮ Algorithmic coincidence classification of mesh patterns ⋮ Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry ⋮ Dynamical aspects of \(\sigma\)-machines ⋮ Bijections between fighting fish, planar maps, and Tamari intervals ⋮ Fighting fish ⋮ Simple permutations and algebraic generating functions ⋮ A bijection between Tamari intervals and extended fighting fish ⋮ Passing through a stack k times ⋮ Operators of equivalent sorting power and related Wilf-equivalences ⋮ Bubblesort, stacksort and their duals ⋮ Fighting fish: enumerative properties ⋮ A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!) ⋮ Baxter permutations and plane bipolar orientations ⋮ Unnamed Item ⋮ Baxter permutations ⋮ New equivalences for pattern avoiding involutions ⋮ Permutations restricted by two distinct patterns of length three ⋮ Two first-order logics of permutations ⋮ On Rearrangement of Items Stored in Stacks ⋮ Passing through a stack \(k\) times with reversals ⋮ A combinatorial proof of J. West's conjecture ⋮ Sorting with two ordered stacks in series. ⋮ Symmetry and unimodality in \(t\)-stack sortable permutations

Cites Work

• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• A Census of Slicings
• A Census of Planar Maps
• Restricted permutations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item