Characterization and Enumeration of Preimages Under the Queuesort Algorithm

Following the footprints of what have been done with the algorithm Stacksort, we investigate the preimages of the map associated with a slightly less well known algorithm, called Queuesort. Our results include a recursive description of the set of all preimages of a given permutation, a characterization of allowed cardinalities for preimages, the exact enumeration of permutations having 0, 1 and 2 preimages, respectively, and, finally, a closed formula for the number of preimages of those permutations whose left-to-right maxima are concentrated at the beginning and at the end.