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

Publication Type:
Journal Article
Electronic Journal of Combinatorics, 2015, 22 (2)
Issue Date:
Full metadata record
© 2015, Australian National University. All rights reserved. We prove that the class of permutations generated by passing an ordered sequence 12... n through a stack of depth 2 and an in nite stack in series is in bi-jection 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:(formula presented) where cn is the number of permutations of length n that can be generated, and (formula presented) is a simple variant of the Catalan generating function. This in turn implies that (formula presented)
Please use this identifier to cite or link to this item: