Permutations sortable by n - 4 passes through a stack

DOI10.1007/S00026-010-0044-7MaRDI QIDQ659583zbMATH OpenOpenAlexFDO

Authors Anders Claesson, Mark Dukes, Einar Steingrímsson

Publication date 24 January 2012

Published in Annals of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

enumerationpatternpermutationstack sorting

Mathematics Subject Classification ID

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

Abstract: We characterise and enumerate permutations that are sortable by n-4 passes through a stack. We conjecture the number of permutations sortable by n-5 passes, and also the form of a formula for the general case n-k, which involves a polynomial expression.

Recommendations

• Passing through a stack k times
• Enumerating permutations sortable by k passes through a pop-stack
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Passing through a stack \(k\) times with reversals
• Enumeration of permutations sorted with two passes through a stack and \(D_{8}\) symmetries

Cites work

• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Permutation tableaux and permutation patterns

Cited in

(19)

• Stack-sorting with consecutive-pattern-avoiding stacks
• Fertility monotonicity and average complexity of the stack-sorting map
• Counting 3-stack-sortable permutations
• Passing through a stack \(k\) times with reversals
• \(k\)-pop stack sortable permutations and \(2\)-avoidance
• Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
• Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture
• Passing through a stack k times
• Highly sorted permutations and Bell numbers
• Asymptotic normality in t-stack sortable permutations
• Enumeration of permutations sorted with two passes through a stack and \(D_{8}\) symmetries
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Enumerating permutations sortable by k passes through a pop-stack
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Promotion sorting
• Deterministic stack-sorting for set partitions
• Periodic points of consecutive-pattern-avoiding stack-sorting maps
• The order of the (123, 132)-avoiding stack sort
• Descent generating polynomials for (n - 3)- and (n - 4)-stack-sortable (pattern-avoiding) permutations

This page was built for publication: Permutations sortable by \(n - 4\) passes through a stack

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