Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution

Simona Grusea (1) , Anthony Labarre (2)

1 IMT - Institut de Mathématiques de Toulouse UMR5219
2 LIGM - Laboratoire d'Informatique Gaspard-Monge

The prefix exchange distance of a permutation is the minimum number of exchanges involving the leftmost element that sorts the permutation. We give new combinatorial proofs of known results on the distribution of the prefix exchange distance for a random uniform permutation. We also obtain expressions for the mean and the variance of this distribution, and finally, we show that the normalised prefix exchange distribution converges in distribution to the standard normal distribution.

Mots clés: star poset; Whitney numbers; combinatorial proofs; permutation; distance; prefix exchange; distribution; asymptotic normality

Domaines: Mathématiques [math]; Combinatoire [math.CO]

Simona Grusea, Anthony Labarre. Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution. Advances in Applied Mathematics, 2016, 78, pp.94-113. ⟨10.1016/j.aam.2016.04.002⟩. ⟨hal-01242140⟩