Probability distribution of number of fixed points of permutations

Definition

Let $n$ be a natural number. Consider the uniform distribution on the symmetric group of degree $n$ . The probability distribution of number of fixed points is the probability distribution on the set ${0, 1, 2, \dots, n}$ where the probability associated with $r$ is the probability that a given permutation has $r$ fixed points.

The probability distribution is given explicitly by:

$P r (n, r) = \frac{D_{n - r}}{r! (n - r)!}$

where $D_{n - r}$ is the derangement number, i.e., the number of permutations on a set of size $n - r$ with no fixed point.

Facts

Expected number of fixed points of permutation equals one: The mean of the distribution is 1.
Expected square of number of fixed points of permutation equals two: The mean of the square of the distribution is 2 (for $n \geq 2$ ).
In general, the expected value of the $k^{t h}$ power of the number of fixed points equals the Bell number $B (k)$ (the number of ways of partitioning a set of size $k$ into subsets) whenever $n \geq k$ ; the above two facts are the special cases $k = 1$ and $k = 2$ . The same proof method as for the above two facts works, but the bookkeeping gets more complicated.

Particular cases

The first table lists number of permutations. The probabilities are obtained by dividing these numbers by $n!$ . The column headers are for number of fixed points.

$n$	$n!$ 0	1	2	3	4	5	6	7	8
1	1	0	1
2	2	1	0	1
3	6	2	3	0	1
4	24	9	8	6	0	1
5	120	44	45	20	10	0	1
6	720	265	264	135	40	15	0	1
7	5040	1854	1855	924	315	70	21	0	1
8	40320	14833	14832	7420	2464	630	112	28	0	1

The second table gives the probabilities:

$n$	0	1	2	3	4	5	6	7	8
1	0	1
2	1/2	0	1/2
3	1/3	1/2	0	1/6
4	3/8	1/3	1/4	0	1/24
5	11/30	3/8	1/6	1/12	0	1/120
6	53/144	11/30	3/16	1/18	1/48	0	1/720
7	103/280	53/144	11/60	1/16	1/72	1/240	0	1/5040
8	2119/5760	103/280	53/288	11/180	1/64	1/360	1/1440	0	1/40320

Computer package implementation

Mathematica implementation

We need the Combinatorica package, that can be loaded using:

<< Combinatorica`

To determine the probability that a permutation on $n$ letters has $r$ fixed points, do:

Binomial[n, r] * NumberOfDerangements[n - r]/Factorial[n]

To output the whole list for a given $n$ , do:

(Binomial[n, #] * NumberOfDerangements[n - #]/Factorial[n]) & /@ Range[0, n]

This can be further mapped for small values of $n$ ; for instance:

f[n_] := (Binomial[n, #] * NumberOfDerangements[n - #]/Factorial[n])  & /@ Range[0, n]

f /@ Range[7]