Skip to content
Enumerating the pop-stacked permutations
C++ Python Shell Makefile
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
f_k_correct
sequence
triangle
README.md
f_k_correct.txt
f_k_guesses.txt
sequence.txt
singularity_estimates.txt
triangle.txt

README.md

Enumerating the pop-stacked permutations

A program to enumerate the pop-stacked permutations. Based on our paper Counting pop-stacked permutations in polynomial time.

Instructions

Navigate into either the sequence directory or the triangle directory, depending on whether you want to count pop-stacked permutations, or pop-stacked permutations grouped by number of ascending runs.

To count permutations up to length N, first perform some initialization by running:

$ python ./init.py N

Then start the computation:

$ ./run_all.sh

Finally, recover the output as follows:

$ python ./combine.py

Sequence

We have already counted the number of pop-stacked permutations of each length up to N=1000. The results can be found in sequence.txt. This is sequence A307030 on OEIS.

Differential approximation

These 1000 terms give insight into the generating function for the number of pop-stacked permutations. Using methods from differential approximation, real and complex singularities of the generating function were approximated to hundreds of digits, and then used to estimate constants in the asymptotic growth of the sequence. The singularity approximations and estimated constants can be found here.

Triangle

We have already counted the number of pop-stacked permutations of each length, grouped by number of ascending runs, up to N=300. The results can be found in triangle.txt, where row K column N is the number of pop-stacked permutations of length N with K ascending runs. This is triangle A309993 on OEIS.

Rational generating functions

Each row, i.e. the number of pop-stacked permutations with a fixed number of ascending runs, is shown to be rational in Pop-stack sorting and its image: permutations with overlapping runs. We used their construction to derive the generating function for the first six rows, but then used our methods to derive conjectures for the first 24 rows.

You can’t perform that action at this time.