Sorting Permutations with Finite-Depth Stacks

Sorting organizes information for optimal usage, and our work examines the mathematics behind sorting with stacks. In 1968, Donald Knuth showed that a permutation is sortable in an infinite-depth stack if and only if it avoids the pattern 231; Knuth also enumerated these permutations. Twenty-five years later, Julian West extended these ideas to permutations sortable with 2 consecutive stacks. We continue this work by limiting the stack(s) to a finite depth. In particular, we completely characterize permutations sortable through a single finite-depth stack and derive a handy enumeration formula. We also apply our pattern characterization and enumeration techniques to permutations that are sortable after k-passes through a finite-depth stack