A Bijection on Classes Enumerated by the Schröder 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 are known to be enumerated by the Schröder numbers. In this pa...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-07-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1326/pdf |
| _version_ | 1827323837530767360 |
|---|---|
| author | Michael W. Schroeder Rebecca Smith |
| author_facet | Michael W. Schroeder Rebecca Smith |
| author_sort | Michael W. Schroeder |
| collection | DOAJ |
| description | 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$. |
| first_indexed | 2024-04-25T01:58:58Z |
| format | Article |
| id | doaj.art-d9ddf14ef6e0468992586d32405e0ef0 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:58Z |
| publishDate | 2017-07-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-d9ddf14ef6e0468992586d32405e0ef02024-03-07T15:30:38ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502017-07-01Vol. 18 no. 2, Permutation...Permutation Patterns10.46298/dmtcs.13261326A Bijection on Classes Enumerated by the Schröder NumbersMichael W. SchroederRebecca SmithWe 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$.https://dmtcs.episciences.org/1326/pdfmathematics - combinatorics05a05 |
| spellingShingle | Michael W. Schroeder Rebecca Smith A Bijection on Classes Enumerated by the Schröder Numbers Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05a05 |
| title | A Bijection on Classes Enumerated by the Schröder Numbers |
| title_full | A Bijection on Classes Enumerated by the Schröder Numbers |
| title_fullStr | A Bijection on Classes Enumerated by the Schröder Numbers |
| title_full_unstemmed | A Bijection on Classes Enumerated by the Schröder Numbers |
| title_short | A Bijection on Classes Enumerated by the Schröder Numbers |
| title_sort | bijection on classes enumerated by the schroder numbers |
| topic | mathematics - combinatorics 05a05 |
| url | https://dmtcs.episciences.org/1326/pdf |
| work_keys_str_mv | AT michaelwschroeder abijectiononclassesenumeratedbytheschrodernumbers AT rebeccasmith abijectiononclassesenumeratedbytheschrodernumbers AT michaelwschroeder bijectiononclassesenumeratedbytheschrodernumbers AT rebeccasmith bijectiononclassesenumeratedbytheschrodernumbers |