Fibonacci enumeration conjecture for simple permutations sortable by two parallel pop stacks

For each n0n\geq 0, let ana_n be the number of simple permutations of size nn that can be sorted by a machine consisting of two pop stacks in parallel, with entries allowed to bypass the pop stacks. Let FnF_n denote the nn-th Fibonacci number.

Fibonacci enumeration conjecture. The sequence (an)(a_n) satisfies

a0=a1=1,a2=2,a_0=a_1=1,\qquad a_2=2, an=F2n51if n3 is odd,a_n=F_{2n-5}-1\quad\text{if $n\geq 3$ is odd}, an=F2n5if n>3 is even.a_n=F_{2n-5}\quad\text{if $n>3$ is even}.

This conjecture proposes a closed form for the enumeration of simple sortable permutations in this two-pop-stack model; the source presents it as a conjecture and gives no evidence of a resolution.

Sources & referencesView supporting material

Primary source

Lapo Cioni, Luca Ferrari and Rebecca Smith, “Sorting permutations using a pop stack with a bypass”, arXiv:2503.08285 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.