A bijection on classes enumerated by the Schröder numbers

Authors

Michael W. Schroeder, Marshall UniversityFollow
Rebecca Smith

Document Type

Article

Publication Date

7-19-2017

Abstract

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.

Comments

The copy of record is available from the publisher at https://dmtcs.episciences.org/3790.

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

Recommended Citation

Schroeder MW, Smith R. A Bijection on classes enumerated by the Schröder numbers. Discrete Mathematics & Theoretical Computer Science. 2017 Jul 19;18:2, 15.