Probability distribution of number of cycles of permutations
Contents
Definition
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.
General information
Average information
Averaging measure | Value | Explanation |
---|---|---|
Mean, i.e., the expected number of cycles | ![]() ![]() ![]() |
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 ![]() |
![]() |
![]() |
![]() |
can only be the identity permutation. |
![]() |
![]() |
![]() |
must be a transposition, determined by picking a subset of size two that gets transposed. |
![]() ![]() |
![]() ![]() ![]() |
![]() |
Particular cases
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:
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
---|---|---|---|---|---|---|---|---|---|
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:
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
---|---|---|---|---|---|---|---|---|
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 ![]() |
Stirling1(n,k)/Factorial(n) | Stirling1, Factorial | Abs[StirlingS1[n,k]]/Factorial[n] | Abs, StirlingS1, Factorial |
List all ![]() ![]() |
List([1..n],k->Stirling1(n,k)/Factorial(n)) | List | (Abs[StirlingS1[n, #]]/Factorial[n]) & /@ Range[n] | Map, Range |