Troupes, cumulants, and stack-sorting

DOI10.1016/J.AIM.2022.108270MaRDI QIDQ2118918zbMATH OpenOpenAlexFDO

Authors Colin Defant

Publication date 23 March 2022

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.11367

zbMATH Keywords

descentfree probabilitycumulantsstack-sortingvalid hook configurationtroupes

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05) Enumeration in graph theory (05C30) Free probability and free operator algebras (46L54)

Abstract: Several sequences of free cumulants that count binary plane trees correspond to sequences of classical cumulants that count the decreasing versions of the same trees. Using two new operations on colored binary plane trees that we call insertion and decomposition, we prove that this surprising phenomenon holds for families of trees that we call troupes. We give a simple characterization of troupes, which provide a broad framework for generalizing several of the results known about West's stack-sorting map $s$. Indeed, we give new proofs of some of the main techniques that have been developed for understanding $s$; these new proofs are far more conceptual than the original ones, explain how the objects called valid hook configurations arise naturally, and generalize to troupes. For $tin2,3$, we enumerate $t$-stack-sortable alternating permutations of odd length and $t$-stack-sortable permutations whose descents are all peaks. The unexpected connection between troupes and cumulants provides a powerful new tool for analyzing the stack-sorting map that hinges on free probability theory. We give numerous applications of this method. For example, we show that if $sigmain{S}_{n-1}$ is chosen uniformly at random, then the expected value of $extdes(s(sigma))+1$ is [left(3-sum_{j=0}^nfrac{1}{j!} ight)n.] Furthermore, the variance of $extdes(s(sigma))+1$ is asymptotically $(2+2e-e^2)n$. We obtain similar results concerning the expected number of descents of postorder readings of decreasing colored binary plane trees. We also obtain improved estimates for $|s(S_n)|$ and an improved lower bound for the degree of noninvertibility of $s$. We give two novel formulas that convert from free to classical cumulants. The first is given by a sum over noncrossing partitions, and the second is given by a sum over $231$-avoiding valid hook configurations. We pose several open problems.

Recommendations

• Troupes, cumulants, and stack-sorting
• Fertilitopes
• Stack-sortable permutations and beyond
• Stack-sorting preimages of permutation classes
• Counting 3-stack-sortable permutations

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 5729471 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 4002828 (Why is no real title available?)
• scientific article; zbMATH DE number 3073237 (Why is no real title available?)
• 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers
• 2-binary trees: bijections and related issues
• A combinatorial proof of J. West's conjecture
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• A simplicial complex of 2-stack sortable permutations
• A survey of alternating permutations
• A survey of stack-sorting disciplines
• Addition of certain non-commuting random variables
• Analytic combinatorics
• Catalan intervals and uniquely sorted permutations
• Combinatorics of permutations
• Contraction-deletion invariants for graphs
• Counting 3-stack-sortable permutations
• Cumulants of the \(q\)-semicircular law, Tutte polynomials, and heaps
• Descents in \(t\)-sorted permutations
• Faces of generalized permutohedra
• Fertilitopes
• Fertility monotonicity and average complexity of the stack-sorting map
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Fighting fish and two-stack sortable permutations
• Free cumulants and enumeration of connected partitions
• Further bijections to pattern-avoiding valid hook configurations
• Generating functions for generating trees
• Hopf algebra of the planar binary trees
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Lectures on the Combinatorics of Free Probability
• Limiting probabilities for vertices of a given rank in 1-2 trees
• Monotone, free, and Boolean cumulants: a shuffle algebra approach
• Multi-static enumeration of two-stack sortable permutations
• Multiplicative functions on the lattice of non-crossing partitions and free convolution
• On linear transformations preserving the Pólya frequency property
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Order structure on the algebra of permutations and of planar binary trees
• Patterns in permutations and words.
• Permutation statistics and linear extensions of posets
• Permutations with forbidden subsequences and nonseparable planar maps
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• Postorder Preimages
• Preimages under the stack-sorting algorithm
• Quantifying noninvertibility in discrete dynamical systems
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Relations between cumulants in noncommutative probability
• Runs, Slides and Moments
• STACS 2005
• Sorted and/or sortable permutations
• Stack-sorting preimages of permutation classes
• Stack-sorting, set partitions, and Lassalle's sequence
• Statistics on lattice walks and \(q\)-Lassalle numbers
• The algebra of binary search trees
• Troupes, cumulants, and stack-sorting
• Two integer sequences related to Catalan numbers
• Unimodality, log-concavity, real-rootedness and beyond
• \(\eta\)-series and a Boolean Bercovici--Pata bijection for bounded \(k\)-tuples

Cited in

(10)

• Troupes, cumulants, and stack-sorting
• Highly sorted permutations and Bell numbers
• Highly sorted permutations with respect to a 312-avoiding stack
• Troupes, cumulants, and stack-sorting
• Lattice paths and \((n - 2)\)-stack sortable permutations
• Deterministic stack-sorting for set partitions
• Fertilitopes
• Preimages under the Queuesort algorithm
• Restricted stacks as functions
• Unimodality of a refinement of Lassalle's sequence

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Troupes, cumulants, and stack-sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118918)