Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution

Autor:	Grusea, Simona, Labarre, Anthony
Rok vydání:	2016
Předmět:	Mathematics - Combinatorics 68R05 05A05 05A15 60F05
Druh dokumentu:	Working Paper
DOI:	10.1016/j.aam.2016.04.002
Popis:	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. Comment: To appear in Advances in Applied Mathematics
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1604.04766 Zobrazit plný text záznamu View this record from Arxiv