# Sorting with two stacks in parallel

Abstract : 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [11 references]

https://hal.inria.fr/hal-01207545
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, October 1, 2015 - 9:28:09 AM
Last modification on : Friday, March 13, 2020 - 12:14:16 PM
Long-term archiving on: : Saturday, January 2, 2016 - 10:36:08 AM

### File

dmAT0151.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01207545, version 1

### Citation

Michael Albert, Mireille Bousquet-Mélou. Sorting with two stacks in parallel. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. pp.585-596. ⟨hal-01207545⟩

Record views