Document Type


Publication Date



We consider a sorting machine consisting of two stacks in series where the first stack has the added restriction that entries in the stack must be in decreasing order from top to bottom. The class of permutations sortable by this machine is known to be enumerated by the Schroder numbers. In this paper, we give a bijection between these sortable permutations of length n and Schroder paths of order n − 1: the lattice paths from (0, 0) to (n − 1, n − 1) composed of East steps (1, 0), North steps (0, 1), and Diagonal steps (1, 1) that travel weakly below the line y = x.


The copy of record is available from the publisher at

Copyright © 2017 by the authors. Distributed under a Creative Commons Attribution 4.0 International License.