Permutations generated by a depth 2 stack and an infinite stack in series are algebraic

Murray Elder¹ ; Geoffrey Lee¹ ; Andrew Rechnitzer²

¹University of Newcastle, Australia
²University of British Columbia

The electronic journal of combinatorics, Tome 22 (2015) no. 2

Résumé

We prove that the class of permutations generated by passing an ordered sequence $12\dots n$ through a stack of depth 2 and an infinite stack in series is in bijection with an unambiguous context-free language, where a permutation of length $n$ is encoded by a string of length $3n$. It follows that the sequence counting the number of permutations of each length has an algebraic generating function. We use the explicit context-free grammar to compute the generating function:\[\sum_{n\geq 0} c_n t^n = \frac{(1+q)\left(1+5q-q^2-q^3-(1-q)\sqrt{(1-q^2)(1-4q-q^2)}\right)}{8q}\]where $c_n$ is the number of permutations of length $n$ that can be generated, and $q \equiv q(t) = \frac{1-2t-\sqrt{1-4t}}{2t}$ is a simple variant of the Catalan generating function. This in turn implies that $c_n^{1/n} \to 2+2\sqrt{5}$.

Détail

DOI : 10.37236/4571

Classification : 05A05, 05A15, 68Q45
Mots-clés : pattern avoiding permutation, algebraic generating function, context-free language