Sorting with two stacks in parallel
At the end of the 1960s, Knuth characterised in terms of forbidden patterns the permutations that can be sorted using a stack. He also showed that they are in bijection with Dyck paths and thus counted by the Catalan numbers. Subsequently, Pratt and Tarjan asked about permutations that can be sorted...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2014-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2425/pdf |
| _version_ | 1827323931568111616 |
|---|---|
| author | Michael Albert Mireille Bousquet-Mélou |
| author_facet | Michael Albert Mireille Bousquet-Mélou |
| author_sort | Michael Albert |
| collection | DOAJ |
| description | At the end of the 1960s, Knuth characterised in terms of forbidden patterns the permutations that can be sorted using a stack. He also showed that they are in bijection with Dyck paths and thus counted by the Catalan numbers. Subsequently, Pratt and Tarjan asked about permutations that can be sorted using two stacks in parallel. This question is significantly harder, and the associated counting question has remained open for 40 years. We solve it by giving a pair of equations that characterise the generating function of such permutations. The first component of this system describes the generating function $Q(a,u)$ of square lattice loops confined to the positive quadrant, counted by the length and the number of North-West and East-South factors. Our analysis of the asymptotic number of sortable permutations relies at the moment on two intriguing conjectures dealing with this series. Given the recent activity on walks confined to cones, we believe them to be attractive $\textit{per se}$. We prove these conjectures for closed walks confined to the upper half plane, or not confined at all. |
| first_indexed | 2024-04-25T02:01:45Z |
| format | Article |
| id | doaj.art-57bff9357b5f41928f4cc74709190a43 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:45Z |
| publishDate | 2014-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-57bff9357b5f41928f4cc74709190a432024-03-07T14:53:18ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502014-01-01DMTCS Proceedings vol. AT,...Proceedings10.46298/dmtcs.24252425Sorting with two stacks in parallelMichael Albert0Mireille Bousquet-Mélou1https://orcid.org/0000-0002-2863-8300Department of Computer Science, University of OtagoLaboratoire Bordelais de Recherche en InformatiqueAt the end of the 1960s, Knuth characterised in terms of forbidden patterns the permutations that can be sorted using a stack. He also showed that they are in bijection with Dyck paths and thus counted by the Catalan numbers. Subsequently, Pratt and Tarjan asked about permutations that can be sorted using two stacks in parallel. This question is significantly harder, and the associated counting question has remained open for 40 years. We solve it by giving a pair of equations that characterise the generating function of such permutations. The first component of this system describes the generating function $Q(a,u)$ of square lattice loops confined to the positive quadrant, counted by the length and the number of North-West and East-South factors. Our analysis of the asymptotic number of sortable permutations relies at the moment on two intriguing conjectures dealing with this series. Given the recent activity on walks confined to cones, we believe them to be attractive $\textit{per se}$. We prove these conjectures for closed walks confined to the upper half plane, or not confined at all.https://dmtcs.episciences.org/2425/pdfpermutationsstacksquarter plane walksgenerating functions[info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co] |
| spellingShingle | Michael Albert Mireille Bousquet-Mélou Sorting with two stacks in parallel Discrete Mathematics & Theoretical Computer Science permutations stacks quarter plane walks generating functions [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| title | Sorting with two stacks in parallel |
| title_full | Sorting with two stacks in parallel |
| title_fullStr | Sorting with two stacks in parallel |
| title_full_unstemmed | Sorting with two stacks in parallel |
| title_short | Sorting with two stacks in parallel |
| title_sort | sorting with two stacks in parallel |
| topic | permutations stacks quarter plane walks generating functions [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/2425/pdf |
| work_keys_str_mv | AT michaelalbert sortingwithtwostacksinparallel AT mireillebousquetmelou sortingwithtwostacksinparallel |