DMTCS Proceedings, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)

Font Size:  Small  Medium  Large

Sorting with two stacks in parallel

Michael Albert, Mireille Bousquet-Mélou

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 per se. We prove these conjectures for closed walks confined to the upper half plane, or not confined at all.
Résumé. Nous &xE;9num&xE;9rons les permutations triables par deux piles en parall&xE;8le. Cette question &xE;9tait rest&xE;9e ouverte depuis les travaux de Knuth, Pratt et Tarjan dans les ann&xE;9es 70. Notre solution consiste en une paire d'&xE;9quations qui caract&xE;9risent la s&xE;9rie g&xE;9n&xE;9ratrice. La premi&xE;8re composante de ce syst&xE;8me d&xE;9crit la s&xE;9rie Q(a,u) des chemins ferm&xE;9s confin&xE;9s dans le quart de plan positif, compt&xE;9s selon leur longueur et le nombre de facteurs Nord-Ouest ou Est-Sud. Notre analyse du comportement asymptotique du nombre de permutations triables repose &xE;0 ce stade sur deux conjectures remarquables portant sur Q(a,u). Nous les prouvons pour les chemins ferm&xE;9s non confin&xE;9s, ou confin&xE;9s au demi-plan sup&xE;9rieur.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional