Permutations Generated by a Depth 2 Stack and an Infinite Stack in Series are Algebraic

Murray Elder, Geoffrey Lee, Andrew Rechnitzer


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 =
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}$.


Pattern avoiding permutation; Algebraic generating function; Context-free language

Full Text: PDF