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

Summary: We prove that the class of permutations generated by passing an ordered sequence \(12\ldots 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\geqslant 0} c_n t^n = \frac{(1+q)\bigg(1+5q-q^2-q^3-(1-q)\sqrt{(1-q^2)(1-4q-q^2)}\bigg)}{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}\).