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

Elder, M; Lee, G; Rechnitzer, A

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

Elder, M

Lee, G Rechnitzer, A

Permalink

Publication Type:: Journal Article
Citation:: Electronic Journal of Combinatorics, 2015, 22 (2)
Issue Date:: 2015-04-29

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (317.35 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.contributor.author	Lee, G	en_US
dc.contributor.author	Rechnitzer, A	en_US
dc.date.issued	2015-04-29	en_US
dc.identifier.citation	Electronic Journal of Combinatorics, 2015, 22 (2)	en_US
dc.identifier.uri	http://hdl.handle.net/10453/97342
dc.description.abstract	© 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 c<inf>n</inf> 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)	en_US
dc.relation.ispartof	Electronic Journal of Combinatorics	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	Permutations generated by a depth 2 stack and an infinite stack in series are algebraic	en_US
dc.type	Journal Article
utslib.citation.volume	2	en_US
utslib.citation.volume	22	en_US
utslib.for	0101 Pure Mathematics	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access
pubs.issue	2	en_US
pubs.publication-status	Published	en_US
pubs.volume	22	en_US

Abstract:

© 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:

http://hdl.handle.net/10453/97342