Local limits of descent-biased permutations and trees

Abstract

We study two related probabilistic models of permutations and trees biased by their number of descents. Here, a descent in a permutation $\sigma$ is a pair of consecutive elements $\sigma (i),\sigma (i+1)$ such that $\sigma (i)>\sigma (i+1)$. Likewise, a descent in a rooted tree with labelled vertices is a pair of a parent vertex and a child such that the label of the parent is greater than the label of the child. For some nonnegative real number $q$, we consider the probability measures on permutations and on rooted labelled trees of a given size where each permutation or tree is chosen with a probability proportional to $q^{\text{number of descents}}$. In particular, we determine the asymptotic distribution of the first elements of permutations under this model. Different phases can be observed based on how $q$ depends on the number of elements $n$ in our permutations. The results on permutations then allow us to characterize the local limit of descent-biased rooted labelled trees.

32 pages