A Bijection on Classes Enumerated by the Schröder Numbers
Authors: Michael W. Schroeder ; Rebecca Smith
NULL##NULL
Michael W. Schroeder;Rebecca Smith
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 are known to be enumerated by the Schröder numbers. In this paper, we
give a bijection between these sortable permutations of length $n$ and
Schröder paths -- 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$.