Michael W. Schroeder ; Rebecca Smith - A Bijection on Classes Enumerated by the Schröder Numbers

dmtcs:1326 - Discrete Mathematics & Theoretical Computer Science, July 19, 2017, Vol. 18 no. 2, Permutation Patterns 2015 - https://doi.org/10.46298/dmtcs.1326
A Bijection on Classes Enumerated by the Schröder NumbersArticle

Authors: 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$.


    Volume: Vol. 18 no. 2, Permutation Patterns 2015
    Section: Permutation Patterns
    Published on: July 19, 2017
    Accepted on: June 7, 2017
    Submitted on: July 16, 2017
    Keywords: Mathematics - Combinatorics,05A05

    Consultation statistics

    This page has been seen 512 times.
    This article's PDF has been downloaded 341 times.