Permutations sortable by n - 4 passes through a stack

DOI10.1007/S00026-010-0044-7zbMATH Open1233.05007arXiv0812.0143OpenAlexW2156069250MaRDI QIDQ659583FDOQ659583

Einar Steingrímsson, Mark Dukes, Anders Claesson

Publication date: 24 January 2012

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

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.

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

zbMATH Keywords

permutationenumerationpatternstack sorting

Mathematics Subject Classification ID

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

Cites Work

• Permutation tableaux and permutation patterns
• Title not available (Why is that?)

Cited In (12)

• Fertility monotonicity and average complexity of the stack-sorting map
• Counting 3-stack-sortable permutations
• Highly sorted permutations and Bell numbers
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Promotion sorting
• Revstack sort, zigzag patterns, descent polynomials of \(t\)-revstack sortable permutations, and Steingrímsson's sorting conjecture
• Passing through a stack k times
• Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Deterministic stack-sorting for set partitions
• Asymptotic normality in t-stack sortable permutations
• Stack-sorting with consecutive-pattern-avoiding stacks

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)