Profiles of permutations

Michael Lugo

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

This paper develops an analogy between the cycle structure of, on the one hand, random permutations with cycle lengths restricted to lie in an infinite set $S$ with asymptotic density $\sigma$ and, on the other hand, permutations selected according to the Ewens distribution with parameter $\sigma$. In particular we show that the asymptotic expected number of cycles of random permutations of $[n]$ with all cycles even, with all cycles odd, and chosen from the Ewens distribution with parameter $1/2$ are all ${1 \over 2} \log n + O(1)$, and the variance is of the same order. Furthermore, we show that in permutations of $[n]$ chosen from the Ewens distribution with parameter $\sigma$, the probability of a random element being in a cycle longer than $\gamma n$ approaches $(1-\gamma)^\sigma$ for large $n$. The same limit law holds for permutations with cycles carrying multiplicative weights with average $\sigma$. We draw parallels between the Ewens distribution and the asymptotic-density case and explain why these parallels should exist using permutations drawn from weighted Boltzmann distributions.

Détail

DOI : 10.37236/188

Classification : 05A15, 05A16, 05A05, 60C05
Mots-clés : number of cycles of random permutations