Troupes, cumulants, and stack-sorting

DOI10.1016/J.AIM.2022.108270zbMATH Open1485.05004arXiv2004.11367OpenAlexW4213101319MaRDI QIDQ2118918FDOQ2118918

Colin Defant

Publication date: 23 March 2022

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (10)

• 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
• Unimodality of a refinement of Lassalle's sequence
• Preimages under the Queuesort algorithm
• Restricted stacks as functions
• Troupes, cumulants, and stack-sorting

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)