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

MaRDI QIDQ2344818zbMATH OpenFDO

Authors Murray Elder, Geoffrey Lee, Andrew Rechnitzer

Publication date 18 May 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.4248, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p16

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

algebraic generating functioncontext-free languagepattern avoiding permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Formal languages and automata (68Q45)

Abstract: We prove that the class of permutations generated by passing an ordered sequence $12dotsn$ 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 language to compute the generating function: �egin{align*} sum_{ngeq 0} c_n t^n &= frac{(1+q)left(1+5q-q^2-q^3-(1-q)sqrt{(1-q^2)(1-4q-q^2)} ight)}{8q} end{align*} where $c_n$ is the number of permutations of length $n$ that can be generated, and $qequivq(t)=frac1-2t-sqrt1-4t2t$ is a simple variant of the Catalan generating function. This in turn implies that $c_n^{1/n}o2+2sqrt5$.

Review text

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}\).

Recommendations

• Permutations generated by a stack of depth 2 and an infinite stack in series
• Permutations sortable by two stacks in series
• Generating permutations with restricted containers
• Multi-static enumeration of two-stack sortable permutations
• Sorting with two ordered stacks in series.

Cites work

• 2-stack sorting is polynomial
• Analytic combinatorics
• Counting 1324, 4231-avoiding permutations
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• On \(1324\)-avoiding permutations
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
• Permutations generated by a stack of depth 2 and an infinite stack in series
• Permutations generated by token passing in graphs
• Permutations sortable by two stacks in parallel and quarter plane walks
• Regular closed sets of permutations.
• Restricted permutations
• Sorting with two ordered stacks in series.
• Symmetric functions and P-recursiveness
• The insertion encoding of permutations

Cited in

(5)

• Generating permutations with restricted containers
• Permutations generated by a stack of depth 2 and an infinite stack in series
• Permutations sortable by two stacks in series
• Combinatorial exploration: an algorithmic framework for enumeration
• Sorting inversion sequences

This page was built for publication: Permutations generated by a depth 2 stack and an infinite stack in series are algebraic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344818)