Random permutation statistics
The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating funct
Wikipage redirect
100 prisoners problemAffine symmetric groupCycle indexDerangementGolomb–Dickman constantInclusion–exclusion principleList of permutation topicsList of statistics articlesMichelle L. WachsRandom Permutation StatisticsRandom permutationRandom permutation statisticsStirling numbers and exponential generating functions in symbolic combinatoricsStirling numbers of the first kindStirling numbers of the second kindSymbolic method (combinatorics)
Link from a Wikipage to another Wikipage
primaryTopic
Random permutation statistics
The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating funct
has abstract
The statistics of random permu ...... uction to random permutations.
@en
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
964,465,320
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
comment
The statistics of random permu ...... compute these generating funct
@en
label
Random permutation statistics
@en