Presentation Type
Poster Presentation
Symposium Date
Spring 4-24-2013
Abstract
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.
Recommended Citation
Goodrich, Timothy; Olson, Will; and Yuan, Ruyue, "Sorting Permutations with Finite-Depth Stacks" (2013). Symposium on Undergraduate Research and Creative Expression (SOURCE). 257.
https://scholar.valpo.edu/cus/257
Biographical Information about Author(s)
Full text link is to abstract only.