Sorting twice through a stack

AbstractWe consider the operation of stack-sorting studied by Knuth. We take the point of view that stack-sorting is a function mapping permutations to permutations, and consider those n-permutations which are sorted by k iterations of this function. Some results are: that all n-permutations are sorted after n − 1 iterations, that (n − 2)! actually require n − 1 iterations, and that a further 72(n − 2)! + (n − 3)! require n − 2 iterations. It has long been known that the permutations sorted after one iteration are the wedge-free permutations, which are counted by the Catalan number (2n)!⧸(n!(n + 1)!). The permutations sorted after two iterations are characterized, and their number conjectured to be 2(3n)!⧸((n + 1)!(2n + 1)!)