Geodesic
Enumerating Permutations Sortable by k Passes Through a Pop-Stack
Séminaire lotharingien de combinatoire, 80B (2018)
Cet article a éte moissonné depuis la source Séminaire Lotharingien de Combinatoire website

Voir la notice de l'acte

In an exercise in the first volume of his famous series of books, Knuth considered sorting permutations by passing them through a stack. Many variations of this exercise have since been considered, including allowing multiple passes through the stack and using different data structures. We are concerned with a variation using pop-stacks that was introduced by Avis and Newborn in 1981. Let Pk(x) be the generating function for the permutations sortable by k passes through a pop-stack. The generating function P2(x) was recently given by Pudwell and Smith (the case k=1 being trivial). We show that Pk(x) is rational for any k. Moreover, we give an algorithm to derive Pk(x), and using it we determine the generating functions Pk(x) for k = 6. 

@article{SLC_2018_80B_a42,
     author = {Anders Claesson and Bjarki \'Ag\'ust Gu{\dh}mundsson},
     title = {Enumerating {Permutations} {Sortable} by k {Passes} {Through} a {Pop-Stack}},
     journal = {S\'eminaire lotharingien de combinatoire},
     year = {2018},
     volume = {80B},
     url = {http://geodesic.mathdoc.fr/item/SLC_2018_80B_a42/}
}
TY  - JOUR
AU  - Anders Claesson
AU  - Bjarki Ágúst Guðmundsson
TI  - Enumerating Permutations Sortable by k Passes Through a Pop-Stack
JO  - Séminaire lotharingien de combinatoire
PY  - 2018
VL  - 80B
UR  - http://geodesic.mathdoc.fr/item/SLC_2018_80B_a42/
ID  - SLC_2018_80B_a42
ER  - 
%0 Journal Article
%A Anders Claesson
%A Bjarki Ágúst Guðmundsson
%T Enumerating Permutations Sortable by k Passes Through a Pop-Stack
%J Séminaire lotharingien de combinatoire
%D 2018
%V 80B
%U http://geodesic.mathdoc.fr/item/SLC_2018_80B_a42/
%F SLC_2018_80B_a42
Anders Claesson; Bjarki Ágúst Guðmundsson. Enumerating Permutations Sortable by k Passes Through a Pop-Stack. Séminaire lotharingien de combinatoire, 80B (2018). http://geodesic.mathdoc.fr/item/SLC_2018_80B_a42/