Probability distribution of number of cycles of permutations

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