Counting Pop-Stacked Permutations in Polynomial Time

DOI10.1080/10586458.2021.1926001MaRDI QIDQ6042966zbMATH OpenOpenAlexFDO

Authors Anders Claesson, Bjarki Agust Gudmundsson, Jay Pantone

Publication date 4 May 2023

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.08910

zbMATH Keywords

automated fittingdifferential approximationenumerationpolynomial time algorithmpop-stacked permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Numerical aspects of recurrence relations (65Q30)

Abstract: Permutations in the image of the pop-stack operator are said to be pop-stacked. 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. Only the first 16 terms had previously been computed. With the 1000 terms we prove some negative results concerning the nature of the generating function for pop-stacked permutations. We also predict the asymptotic behavior of the counting sequence using differential approximation.

Recommendations

• The enumeration of permutations sortable by pop stacks in parallel
• Stack-sortable permutations and polynomials
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Enumerating permutations sortable by k passes through a pop-stack
• The complexity of counting poset and permutation patterns
• Stack-sortable permutations and beyond
• Counting Stirling permutations by number of pushes
• \(k\)-pop stack sortable permutations and \(2\)-avoidance
• Multi-static enumeration of two-stack sortable permutations
• A survey of stack sortable permutations

Cites work

• A stack and pop stack in series
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Extended rate, more GFUN
• GFUN
• High-order differential approximants
• scientific article; zbMATH DE number 3722110 (Why is no real title available?)
• Pop-stacks in parallel
• Series analysis
• Two-stack-sorting with pop stacks

Cited in

(15)

• Pop-stacks in parallel
• Finding and counting permutations via CSPs
• Meeting covered elements in -Tamari lattices
• Counting 3-stack-sortable permutations
• Efficient methods of calculating the number of heapable permutations
• Pop-stack-sorting for Coxeter groups
• Stack-sorting for Coxeter groups
• Enumerating permutations sortable by k passes through a pop-stack
• The image of the pop operator on various lattices
• Semidistrim Lattices
• The Ungar games
• Foot-sorting for socks
• Pop-stack sorting and its image: permutations with overlapping runs
• A new lower bound for deterministic pop-stack-sorting
• Dynamics of pop-tsack torsing

This page was built for publication: Counting Pop-Stacked Permutations in Polynomial Time

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