Enumerating permutations sortable by \(k\) passes through a pop-stack

DOI10.1016/j.aam.2019.04.002zbMath1415.05012arXiv1710.04978OpenAlexW2963004472WikidataQ128019663 ScholiaQ128019663MaRDI QIDQ5918174

Anders Claesson, Bjarki Agust Gudmundsson

Publication date: 11 July 2019

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

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

zbMATH Keywords

generating functionenumerationpermutationrationalautomatonpop-stack

Mathematics Subject Classification ID

Searching and sorting (68P10) Exact enumeration problems, generating functions (05A15) Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (14)

Crystal pop-stack sorting and type \(A\) crystal lattices ⋮ Pop-stack-sorting for Coxeter groups ⋮ Stack-sorting for Coxeter groups ⋮ Coxeter pop-tsack torsing ⋮ Sorting Cayley permutations with pattern-avoiding machines ⋮ The pop-stack-sorting operator on Tamari lattices ⋮ Counting Pop-Stacked Permutations in Polynomial Time ⋮ Ungarian Markov chains ⋮ The image of the pop operator on various lattices ⋮ Semidistrim Lattices ⋮ Semidistrim lattices ⋮ Fertility monotonicity and average complexity of the stack-sorting map ⋮ Unnamed Item ⋮ Meeting covered elements in \(\nu\)-Tamari lattices

Uses Software

• MapReduce
• SageMath

Cites Work

• Unnamed Item
• Unnamed Item
• Fast brief practical DFA minimization
• Permutations sortable by two stacks in parallel and quarter plane walks
• Describing West-3-stack-sortable permutations with permutation patterns
• The enumeration of permutations sortable by pop stacks in parallel
• 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)\)!)
• Pop-stacks in parallel
• Restricted permutations and the wreath product
• The insertion encoding of permutations
• On the definition of a family of automata
• Two-stack-sorting with pop stacks
• Sorting Using Networks of Queues and Stacks
• Enumerating permutations sortable by \(k\) passes through a pop-stack

This page was built for publication: Enumerating permutations sortable by \(k\) passes through a pop-stack