<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Permutations Sortable by n-4 Passes Through a Stack
Anders Claesson1, Mark Dukes2, and Einar Steingrímsson1
1The Mathematics Institute, Reyjavík University, 103 Reykjavík, Iceland
anders@ru.is, einar@alum.mit.edu
2Science Institute, University of Iceland, 107 Reykjavík, Iceland
dukes@hi.is
Annals of Combinatorics 14 (1) pp.45-51 Springer, 2010
AMS Subject Classification: 05A15, 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.
Keywords: permutation, stack sorting, pattern, enumeration

References:

1. Knuth, D.E.: The Art of Computer Programming. Vol. 1: Fundamental Algorithms. Addison-Wesley Publishing Co., Reading, Mass. (1969)

2. Steingrímsson, E.: Generalized Permutation Patterns — a Short Survey. In: Linton, S.A., Ruskuc, N., Vatter, V. (eds.) “Permutation Patterns, St Andrews 2007”, LMS Lecture Note Series. Cambridge University Press, Cambridge, to appear

3. West, J.: Permutations with Forbidden Subsequences; and, Stack Sortable Permutations. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge (1990)