A Bijection on Classes Enumerated by the Schroder Numbers

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.