Document Type

Poster Presentation

Celebration Date

Spring 4-24-2013


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.

Biographical Information about Author(s)

Full text link is to abstract only.