In an exercise in the first volume of his famous series of books, Knuthconsidered sorting permutations by passing them through a stack. Manyvariations of this exercise have since been considered, including allowingmultiple passes through the stack and using different data structures. We areconcerned with a variation using pop-stacks that was introduced by Avis andNewborn in 1981. Let $P_k(x)$ be the generating function for the permutationssortable by $k$ passes through a pop-stack. The generating function $P_2(x)$was recently given by Pudwell and Smith (the case $k=1$ being trivial). We showthat $P_k(x)$ is rational for any $k$. Moreover, we give an algorithm to derive$P_k(x)$, and using it we determine the generating functions $P_k(x)$ for$kleq 6$.
展开▼
机译：在他着名的一系列着名书籍的第一卷的运动中，通过将它们通过堆叠来排序排列。此练习的许多高变为已被考虑，包括允许多次通过堆栈并使用不同的数据结构。我们在1981年使用Avis Andnewborn引入的POP堆栈中的变体进行了变化。让$ P_K（x）$是禁用的发电功能，通过POP堆栈通过$ K $传递。 PUDWELL和SMITH最近给出的生成函数$ P_2（x）$（案例$ k = 1 $琐碎）。我们为您的价格提供$ p_k（x）$合理的任何$ k $。此外，我们给出了算法来派生$ p_k（x）$，并使用它来确定生成函数$ p_k（x）$ for k leq 6 $。
展开▼
