Séminaire Lotharingien de Combinatoire, 86B.16 (2022), 12 pp.
Colin Defant
Troupes, Cumulants, and Stack-Sorting
Abstract.
In several cases, a sequence of free cumulants that counts certain binary plane trees corresponds to a sequence of classical cumulants that counts the decreasing versions of the same trees. Using two new operations on binary plane trees that we call insertion and decomposition, we prove that this surprising phenomenon holds for families of trees that we call troupes. The proof relies on two new formulas, each of which is given as a sum over objects called valid hook configurations. The first of these formulas provides detailed information about the preimages of a permutation under the postorder traversal that lie in a given troupe; the second is a new combinatorial formula that converts from a sequence of free cumulants to the corresponding sequence of classical cumulants. The unexpected connection between troupes and cumulants provides a powerful new tool for analyzing the stack-sorting map s (which is defined via the postorder traversal) that hinges on free probability theory. We give numerous applications of this method. For example, we show that if σ in Sn-1 is chosen uniformly at random and des denotes the descent statistic, then the expected value of des(s(σ))+1 is
Furthermore, the variance of des(s(σ))+1 is asymptotically (2+2e-e^2)n. We obtain similar results concerning the expected number of descents of postorder readings of decreasing binary plane trees of various types. We also obtain improved estimates for |s(Sn)| and an improved lower bound for the degree of noninvertibility of s : Sn -> Sn.
Received: November 25, 2021.
Accepted: March 4, 2022.
Final version: April 1, 2022.
The following versions are available: