Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution

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 expressio...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-04
Main Authors: Grusea, Simona, Labarre, Anthony
Format: Article
Language:English
Subjects:
Combinatorial analysis
Exchanging
Normal distribution
Normality
Permutations
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1604.04766