Málstofa í stærðfræði

Fyrirlesari: Bjarki Ágúst Guðmundsson, University of Iceland

Titill: Enumerating permutations sortable by k passes through a pop-stack

Staðsetning: VRII-158
Tími: Mánudagur 18. september kl. 15:00

Ágrip:

In an exercise in the first volume of his famous series of books, Knuth considered sorting permutations by passing them through a stack. He noted that, out of the \(n!\) permutations on \(n\) elements, \(C_n\) of them can be sorted by a single pass through a stack, where \(C_n\) is the \(n\)-th Catalan number. Many variations of this exercise have since been considered, including allowing multiple passes through the stack and using different data structures. West classified the permutations that are sortable by 2 passes through a stack, and a formula for the enumeration was later proved by Zeilberger. The permutations sortable by 3 passes through a stack, however, have yet to be enumerated. We consider a variation of this exercise using pop-stacks. For any fixed \(k\), we give an algorithm to derive a generating function for the permutations sortable by \(k\) passes through a pop-stack. Recently the generating function for \(k=2\) was given by Pudwell and Smith (the case \(k=1\) being trivial). Running our algorithm on a computer cluster we derive the generating functions for \(k\) at most 6. We also show that, for any \(k\), the generating function is rational.