Probability distribution of number of cycles of permutations
Let be a natural number. Denote by the symmetric group of degree . Consider the uniform probability measure on (i.e., the normalized counting measure, under which the measure of any subset is the quotient of the size of the subset by ). The probability distribution of number of cycles of permutations is the probability distribution that assigns, to all numbers , the probability that a permutation picked uniformly at random from has exactly cycles in its cycle decomposition.
Note that in the count of cycles, each fixed point is treated as one cycle. Thus, the identity permutation has cycles whereas a cyclic permutation that moves all elements involves cycle.
The probability distribution assigns the following value to each
where is the unsigned Stirling number of the first kind, and occurs as an important combinatorial quantity. It can also be defined as the sum, over all unordered partitions of into parts, of the sizes of the conjugacy classes corresponding to each part.
|Mean, i.e., the expected number of cycles||, the harmonic number of , which is the sum of reciprocals of the first natural numbers||Expected number of cycles of permutation equals harmonic number of degree|
Formulas in special cases
|Case for||Value of||Probability, i.e., value of||Explanation|
|must be a cyclic permutation with one cycle of size , then use conjugacy class size formula for symmetric group.|
|can only be the identity permutation.|
|must be a transposition, determined by picking a subset of size two that gets transposed.|
|, odd||, where is the harmonic number, i.e., the sum of reciprocals of first natural numbers|
The unsigned Stirling number of the first kind for any given form a unimodal sequence, hence the corresponding probability distribution is also unimodal (i.e., single-peaked).
Here is the table of unsigned Stirling numbers:
Here is the table of probability values:
Computer package implementation
All unbounded variables are either defined beforehand or are replaced by actual numerical values.
|Goal||GAP command||GAP functions used||Mathematica command||Mathematica functions used|
|Find||Stirling1(n,k)/Factorial(n)||Stirling1, Factorial||Abs[StirlingS1[n,k]]/Factorial[n]||Abs, StirlingS1, Factorial|
|List all , fixed||List([1..n],k->Stirling1(n,k)/Factorial(n))||List||(Abs[StirlingS1[n, #]]/Factorial[n]) & /@ Range[n]||Map, Range|