Counting Pop-Stacked Permutations in Polynomial Time

Abstract

Permutations that can be sorted greedily by one or more stacks having various constraints have been studied by a number of authors. A pop-stack is a greedy stack that must empty all entries whenever popped. Permutations in the image of the pop-stack operator are said to be pop-stacked. Asinowki, Banderier, Billey, Hackl, and Linusson recently investigated these permutations and calculated their number up to length 16. We give a polynomial-time algorithm to count pop-stacked permutations up to a fixed length and we use it to compute the first 1000 terms of the corresponding counting sequence. With the 1000 terms, we apply a pair of computational methods to prove some negative results concerning the nature of the generating function for pop-stacked permutations and to empirically predict the asymptotic behavior of the counting sequence using differential approximation.

Keywords:

• Enumeration
• pop-stacked permutation
• polynomial time algorithm
• automated fitting
• differential approximation

MSC 2010::

• 05A15
• 65Q30
• 68R05

Acknowledgments

Computations were performed on the Garpur cluster [9], a joint project between the University of Iceland and the University of Reykjavik funded by the Icelandic Centre for Research. We thank them for the use of their resources.

Declaration of Interest

No potential conflict of interest was reported by the author(s).