Counting Pop-Stacked Permutations in Polynomial Time

作     者：Claesson, Anders Guomundsson, Bjarki agust Pantone, Jay 

作者机构：Univ Iceland Inst Sci Div Math Reykjavik Iceland Reykjavik Univ Dept Comp Sci Reykjavik Iceland Marquette Univ Dept Math & Stat Sci Milwaukee WI 53233 USA 

出 版 物：《EXPERIMENTAL MATHEMATICS》 (实验数学)

年 卷 期：2023年第32卷第1期

页      面：97-104页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Icelandic Centre for Research 

主　　题：Enumeration pop-stacked permutation polynomial time algorithm automated fitting differential approximation 

摘      要：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.