Probability distribution of number of cycles of permutations

From Groupprops
Jump to: navigation, search

Definition

Let n be a natural number. Denote by S_n the symmetric group of degree n. Consider the uniform probability measure on S_n (i.e., the normalized counting measure, under which the measure of any subset is the quotient of the size of the subset by n!). The probability distribution of number of cycles of permutations is the probability distribution that assigns, to all numbers 1 \le k \le n, the probability that a permutation picked uniformly at random from S_n has exactly k 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 n cycles whereas a cyclic permutation that moves all elements involves 1 cycle.

The probability distribution assigns the following value to each k

\! \frac{|s(n,k)|}{n!}

where |s(n,k)| 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 n into k parts, of the sizes of the conjugacy classes corresponding to each part.

General information

Average information

Averaging measure Value Explanation
Mean, i.e., the expected number of cycles H_n, the harmonic number of n, which is the sum of reciprocals of the first n natural numbers Expected number of cycles of permutation equals harmonic number of degree

Formulas in special cases

Case for (n,k) Value of |s(n,k)| Probability, i.e., value of |s(n,k)|/n! Explanation
(n,1) (n - 1)! 1/n must be a cyclic permutation with one cycle of size n, then use conjugacy class size formula for symmetric group.
(n,n) 1 1/n! can only be the identity permutation.
(n,n-1) \binom{n}{2} = \frac{n(n-1)}{2} \frac{1}{2[(n-2)!]} must be a transposition, determined by picking a subset of size two that gets transposed.
(n,2), n odd (n - 1)! H_{n-1}, where H_{n-1} is the harmonic number, i.e., the sum of reciprocals of first n - 1 natural numbers H_{n-1}/n \approx (\log n)/n

Particular cases

The unsigned Stirling number of the first kind for any given n form a unimodal sequence, hence the corresponding probability distribution is also unimodal (i.e., single-peaked).

Here is the table of unsigned Stirling numbers:

n n! |s(n,1)| |s(n,2)| |s(n,3)| |s(n,4)| |s(n,5)| |s(n,6)| |s(n,7)| |s(n,8)|
1 1 1
2 2 1 1
3 6 2 3 1
4 24 6 11 6 1
5 120 24 50 35 10 1
6 720 120 274 225 85 15 1
7 5040 720 1764 1624 735 175 21 1
8 40320 5040 13068 13132 6769 1960 322 28 1

Here is the table of probability values:

n k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8
1 1
2 1/2 1/2
3 1/3 1/2 1/6
4 1/4 11/24 1/4 1/24
5 1/5 5/12 7/24 1/12 1/120
6 1/6 137/360 5/16 17/144 1/48 1/720
7 1/7 7/20 29/90 7/48 5/144 1/240 1/5040
8 1/8 363/1120 469/1440 967/5760 7/144 23/2880 1/1440 1/40320

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 |s(n,k)|/n! Stirling1(n,k)/Factorial(n) Stirling1, Factorial Abs[StirlingS1[n,k]]/Factorial[n] Abs, StirlingS1, Factorial
List all |s(n,k)|/n!, fixed n List([1..n],k->Stirling1(n,k)/Factorial(n)) List (Abs[StirlingS1[n, #]]/Factorial[n]) & /@ Range[n] Map, Range