Séminaire Lotharingien de Combinatoire, 84B.4 (2020), 12 pp.

Colin Defant

Uniquely Sorted Permutations

Abstract. 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 several conjectures.

Received: November 20, 2019. Accepted: February 20, 2020. Final version: April 30, 2020.

The following versions are available: