Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution

DOI10.1016/J.AAM.2016.04.002MaRDI QIDQ281902zbMATHOpenAlexFDO

Authors Simona Grusea, Anthony Labarre

Publication date 11 May 2016

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

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

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)

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.

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

Cites work

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

Cited in

(3)

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

Describes a project that uses

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)