Article ID Journal Published Year Pages File Type
4624518 Advances in Applied Mathematics 2016 20 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, ,