Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution

DOI10.1016/J.AAM.2016.04.002zbMATH Open1358.05008arXiv1604.04766OpenAlexW2963684686MaRDI QIDQ281902FDOQ281902

Authors: Simona Grusea, Anthony Labarre 

Publication date: 11 May 2016

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1604.04766

Recommendations

• Central limit theorem for the prefix exchange distance under Ewens sampling formula
• Limit distribution of ascent, descent or excedance length sums of permutations
• A coupling proof of the asymptotic normality of the permutation oscillation
• On the limiting distribution for the length of the longest alternating sequence in a random permutation
• The cycle structure of random permutations

zbMATH Keywords

asymptotic normalitydistributionpermutationdistancecombinatorial proofsprefix exchangestar posetWhitney numbers

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Central limit and other weak theorems (60F05) Exact enumeration problems, generating functions (05A15)

Cites Work

• Generatingfunctionology
• Title not available (Why is that?)
• Title not available (Why is that?)
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A group-theoretic model for symmetric interconnection networks
• Central and local limit theorems applied to asymptotic enumeration
• Combinatorics of permutations
• Some topological properties of star graphs: The surface area and volume
• The asymptotic expansion of a ratio of gamma functions
• Title not available (Why is that?)
• Combinatorics of genome rearrangements.
• Gaussian limiting distributions for the number of components in combinatorial structures
• Patterns in permutations and words.
• Whitney numbers of the second kind for the star poset
• On the Whitney numbers of the second kind for the star poset

Cited In (3)

• Central limit theorem for the prefix exchange distance under Ewens sampling formula
• A coupling proof of the asymptotic normality of the permutation oscillation
• Sorting on graphs by adjacent swaps using permutation groups

Uses Software

• OEIS

This page was built for publication: Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281902)