# Probability distribution of number of fixed points of permutations

## Contents

## Definition

Let be a natural number. Consider the uniform distribution on the symmetric group of degree . The probability distribution of number of fixed points is the probability distribution on the set where the probability associated with is the probability that a given permutation has fixed points.

The probability distribution is given explicitly by:

where is the derangement number, i.e., the number of permutations on a set of size with no fixed point.

The mean (expected value) of this distribution is one. `Further information: expected number of fixed points of permutation equals one`

## Particular cases

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

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:

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 letters has fixed points, do:

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

To output the whole list for a given , do:

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

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

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