2014/07/16 by Murray Elder, Elder, Murray, Geoffrey Lee +3
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05A05 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Biochemical and Structural Characterization #Botanical Research and Chemistry #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1407.4248
openalex publication_date 2014/07/16 · openalex created_date 2022/08/27 · openalex updated_date 2026/07/28
We prove that the class of permutations generated by passing an ordered\nsequence 12\… n through a stack of depth 2 and an infinite stack in series\nis in bijection with an unambiguous context-free language, where a permutation\nof length n is encoded by a string of length 3n. It follows that the\nsequence counting the number of permutations of each length has an algebraic\ngenerating function. We use the explicit context-free language to compute the\ngenerating function: \
sumn
geq 0 cn tn amp;=\n
frac(1+q)
left(1+5q-q2-q3-(1-q)
sqrt(1-q2)(1-4q-q2)
right)8q\n where cn is the number of permutations of length n that can\nbe generated, and q \≡ q(t) = \(1-2t-\√(1-4t))/(2t) is a simple\nvariant of the Catalan generating function. This in turn implies that\ncn1/n \→ 2+2\√(5).\n