Open Neighborhood Seminar: Stack-Sorting and Beyond

In 1990, West introduced the stack-sorting map, a combinatorially-defined operator on the set of permutations of size n that serves as a deterministic analogue of Knuth's stack-sorting machine. I will discuss a method for computing the fertility of an arbitrary permutation, which is simply the number of preimages of the permutation under the stack-sorting map. This method uses combinatorial objects called valid hook configurations. Very surprisingly, valid hook configurations also appear in a formula that converts from free to classical cumulants in free probability theory. This allows us to use tools from free probability theory to prove deep facts about the stack-sorting map. On the other hand, we can also leverage the stack-sorting map to prove a new theorem that relates cumulants with special families of binary plane trees called troupes. This talk will be very elementary and combinatorial, and I will probably mention some open problems at the end.