The enumeration of permutations sortable by pop stacks in parallel

With Rebecca Smith.

Information Processing Letters, 109 (2009), 626–629.

We show that the set of permutations sortable by k pop stacks in parallel has a regular insertion encoding and construct the (finite) recognizing automaton for this language. This shows that these permutations have a rational generating function, verifying a conjecture of Atkinson and Sack.

Download the paper:

• download from the journal
• pdf
• source

Related links:

• The Maple package POPSTACKS implements our automata.
• The permutations that can be sorted by 2 pop stacks in parallel are counted by sequence A164870 in the OEIS.
• The permutations that can be sorted by 3 pop stacks in parallel are counted by sequence A164871 in the OEIS.
• The permutations that can be sorted by 4 pop stacks in parallel are counted by sequence A164872 in the OEIS.
• The permutations that can be sorted by 5 pop stacks in parallel are counted by sequence A164873 in the OEIS.

< back to homepage