Séminaire Lotharingien de Combinatoire, 84B.4 (2020), 12 pp.
Uniquely Sorted Permutations
We say a permutation is uniquely sorted if it has exactly 1
preimage under West's stack-sorting map. In this extended abstract, we
describe some of the rich enumerative structure that the set of such
permutations possesses. After stating a characterization of uniquely
sorted permutations, we study their enumeration, which is given by
Lassalle's sequence and is connected to free probability theory. We
then consider five well-studied classes of posets defined on Dyck
paths, establishing bijections between uniquely sorted permutations
that avoid various patterns and intervals in these posets. We end with
Received: November 20, 2019.
Accepted: February 20, 2020.
Final version: April 30, 2020.
The following versions are available: