Permutations sortable by n - 4 passes through a stack

Anders Claesson*, Mark Dukes, Einar Steingrímsson

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)45-51
Number of pages7
JournalAnnals of Combinatorics
Volume14
Issue number1
DOIs
Publication statusPublished - Mar 2010

Bibliographical note

Funding Information:
∗ Supported by grant no. 060005013 from the Icelandic Research Fund. †The author acknowledges funding by the EC’s Research Training Network ‘Algebraic Combinatorics in Europe’, grant HPRN-CT-2001-00272 while at Université Bordeaux 1, France. ‡Supported by grant no. 060005013 from the Icelandic Research Fund.

Other keywords

  • Enumeration
  • Pattern
  • Permutation
  • Stack sorting

Fingerprint

Dive into the research topics of 'Permutations sortable by n - 4 passes through a stack'. Together they form a unique fingerprint.

Cite this