Fixed Points in Random Permutations

0. Introduction and problem statement

A standard question in probability theory and combinatorics is to determine the probability of having a specific number of fixed points in a random permutation. For instance, a real life problem that features this question is given in [1, Chapter 2 Exercises] and reads as follows.

Suppose $n$ people leave their coats at the the theatre wardrobe prior to the show and, due to a power outage, they each get handed a coat randomly in the dark later. What is the probability that $k \leq n$ people then have their own coat?

There are several interesting approaches to solving this and recently, I found another one that reminded me of Fibonacci numbers. With those you have the relationship

\begin{equation} f_{n + 1} = f_{n} + f_{n - 1}, \qquad\qquad f_2 = 1 = f_1, n \geq 2
\end{equation}

that can be transformed into the matrix representation

\begin{equation} \begin{pmatrix} f_{n + 1} \\ f_{n} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f_n \\ f_{n - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} f_2 \\ f_{1} \end{pmatrix} \end{equation}

Diagonalizing that matrix then gives an explicit expression for $f_{n + 1}$.

In the following I’ll show that a similar recurrence relation also holds for the number of fixed points in a permutation.

1. Definitions and Notation

First, we define the necessary terminology and notation.

Definition. A bijective function $\pi: \{1, \ldots, n\} \to \{1, \ldots, n\}$ is called a permutation.

For $n = 3$, an example for a permutation would be $1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 1$ or

$$ \pi(1) = 2, \pi(2) = 1, \pi(3) = 2 $$

A common way to denote permutations is by way of permutation tables, e.g. $\pi = \Big(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{smallmatrix}\Big)$.

Definition. A fixed point of a permutation $\pi$ is an element $l \in \{1, \ldots, n\}$ for which it holds that $\pi(l) = l$.

For example, there are no fixed points in the above permutation because $\pi(l) \neq l$ for all $l \in \{1, \ldots, 3\}$.

To derive the probability of having $k$ fixed points in a permutation we need to set up (i). an appropriate probability space $(\Omega, \mathcal{A}, P)$ and (ii). a random variable $X$ that maps permutations to the number of permutations $k$.

(i). Obviously, it is $\Omega = \mathscr{S}^n$ as we care about permutations and $\mathscr{S}^n$ is the set of all permutations with $n$ elements. Since it clearly holds that $\vert \mathscr{S}^n \vert = n! < \infty$ for $n < \infty$, we set $\mathcal{A} = \mathcal{P}(\mathscr{S}^n)$. Furthermore, we assume that each permutation is equally likely to occur, i.e., uniformly distributed. Hence, $P_{\Omega} = \mathcal{U}_{\Omega}$.

(ii). Consider the random variable $X: \mathscr{S}^n \to \{0, \ldots, n\}$ mit $X(\pi) = \sum\limits_{i = 1}^{N} 1_{{i = \pi(i)}}$. It maps each permutation to its number of fixed points and is thus appropriate for our task.

2. Solving the problem theoretically

Because of the uniformness distribution on $\mathscr{S}^n$ with $P_{\Omega} = \mathcal{U}_{\Omega}$ and according to basic results of probability theory it holds that \begin{equation} P_{X}(k) = P_{\Omega}(X^{-1}(k)) = \frac{\vert X(\omega) = k\vert}{\vert \Omega \vert} = \frac{\vert X(\omega) = k\vert}{n!} \end{equation} according to basic results of probability theory.

The problem now reduces to deriving an explicit expression for $\vert X(\pi) = k\vert$, i.e. the number of permutations of $n$ elements that exhibit $k$ fixed points.

Define $T^{0, n}$ as the number of permutations of $n$ elements without any fixed points. These are all permutations that don’t have exactly one fixed point, exactly two fixed points, $\ldots$, exactly $n - 1 = n$ fixed points.

To construct a permutation with exactly one fixed point, we fix one element and permutate the remaining $n - 1$ elements in such a way that there no fixed points. There are $T^{0, n - 1}$ permutations to choose from. Since you can choose $\binom{n}{1} = n$ different 1-element sets out of $n$ elements, there in total $\binom{n}{1}T^{0, n - 1}$ permutations that exhibit exactly one fixed point. Analogously, there are $\binom{n}{2}T^{0, n - 2}$ permutations that have exactly two fixed points and so on for any $k \leq n$.

Since for $n$ elements, there are $n!$ permutations in total, we can recover the number of fixed-point free permutations of $n$ elements as

\begin{equation} T^{0, n} = n! - \binom{n}{1}T^{0, n - 1} - \binom{n}{2}T^{0, n - 2} - \ldots \end{equation}

Here the connection to Fibonacci numbers emerges. The expression above is recursive. Therefore, we’ll transform the equation into matrix format,

\begin{equation} \overrightarrow{T} = \begin{pmatrix} T^{0, n} \\
T^{0, n - 1} \\\ \vdots \\
T^{0, 1} \end{pmatrix} = \begin{pmatrix} n! \\
(n - 1)! \\\ \vdots \\
1 \end{pmatrix} -\begin{pmatrix} 0 & \binom{n}{1} & \binom{n}{2} & \ldots & 1 \\
0 & 0 & \binom{n - 1}{1} & \ldots & 1 \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
0 & 0 & \ldots & 0 & 1 \end{pmatrix} \begin{pmatrix} T^{0, n} \\
T^{0, n - 1} \\\ \vdots \\
T^{0, 1} \end{pmatrix} \end{equation}

Some algebraic manipulations give

\begin{equation} \overrightarrow{T} = \underbrace{\begin{pmatrix} 1 & \binom{n}{1} & \binom{n}{2} & \ldots & 1 \\
0 & 1 & \binom{n - 1}{1} & \ldots & 1 \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
0 & 0 & \ldots & 0 & 1 \end{pmatrix}^{-1}}_{A^{-1}} \begin{pmatrix} n! \\
(n - 1)! \\\ \vdots \\
1 \end{pmatrix} \qquad \qquad (1) \end{equation}

Note that $\det(A) = \lambda_1\cdot \ldots\cdot \lambda_n$. But since $A$ is diagonal, the eigenvalues are the diagonal elements and as such $\det(A) = 1 > 0$, i.e. $A$ is indeed invertible!

But $A$ is the so-called Pascal matrix with known inverse \begin{equation} A^{-1} = \begin{pmatrix} 0 & \binom{n}{1} & \binom{n}{2} & \ldots & 1 \\
0 & 0 & \binom{n - 1}{1} & \ldots & 1 \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
0 & 0 & \ldots & 0 & 1 \end{pmatrix}^{-1} = \begin{pmatrix} 0 & - \binom{n}{1} & \binom{n}{2} & \ldots & 1 \\
0 & 0 & -\binom{n - 1}{1} & \ldots & 1 \\
\vdots & \vdots & \vdots & \vdots & \vdots \\\ 0 & 0 & \ldots & 0 & 1 \end{pmatrix} = (-1)^{j + 1}A_{ij} \end{equation}

After multiplying the inverse with the vector on the right-hand side in (1), we arrive at

\begin{equation} T^{0, n} = \sum\limits_{i = 0}^{n} (-1)^{i}\binom{n}{i}(n - i)! \end{equation}

Finally, the number of permutations with $k$ fixed points is now immediately derived as

\begin{equation} \vert {X = k}\vert = \binom{n}{k}T^{0, n - k} = \binom{n}{k}\sum\limits_{i = 0}^{n - k} (-1)^{i}\binom{n - k}{i} (n - k - i)! \end{equation}

and with it the desired probability as

\begin{align} P_{X}(k) &= P_{\Omega}(X^{-1}(k)) \\
&= \frac{\vert X(\pi) = k\vert}{\vert \mathscr{S}^n \vert} \\
&= \frac{\vert X(\pi) = k\vert}{n!} \\
&= \frac{\binom{n}{k}\sum\limits_{i = 0}^{n - k} (-1)^{i}\binom{n - k}{i} (n - k - i)!}{n!} \\
&= \frac{1}{k!(n - k)!}\sum\limits_{i = 0}^{n - k}(-1)^i\binom{n - k}{i}(n - k - i)! \\
&= \frac{1}{k!(n - k)!}\sum\limits_{i = 0}^{n - k}(-1)^i\frac{(n - k)!}{i!(n - k - i)!}(n - k - i)! \\
&= \frac{1}{k!}\sum\limits_{i = 0}^{n - k} (-1)^i\frac{1}{i!} \end{align}

To return to the initial real-life application. For $n = 5$ coats und $k = 1$, i.e. only one person receives her own coat, the probability reads as

\begin{equation} P_X(1) = \frac{1}{1!}\sum\limits_{i = 0}^{4} (-1)^i \frac{1}{i!} = 1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} = \frac{9}{24} = 37.5\%
\end{equation}

3. Solving the problem computationally

The following R code produces simulation results that closely resemble the theoretical assertions.

Anzahl.Mantel = 5
Anzahl.Rep = 1000

Mantel = replicate(Anzahl.Rep, {
sample(1:Anzahl.Mantel, Anzahl.Mantel, replace = FALSE)
})

Test = matrix(1:Anzahl.Mantel, nrow = Anzahl.Mantel, ncol = Anzahl.Rep)

Vergleich = (Mantel == Test) %>% 
                  t() %>% 
             as.data.frame() %>%
             mutate(Anzahl = rowSums(.))

table(Vergleich$Anzahl)/sum(table(Vergleich$Anzahl))

The resulting distribution is as follows.

> table(Vergleich$Anzahl)/sum(table(Vergleich$Anzahl))

0     1     2     3     5 
0.397 0.365 0.149 0.079 0.010 

The difference to the true theoretical results is hence small after already 1000 draws.

4. Epilogue

It can be shown that the number of fixed points $k$ in a permutation of $n$ elements is poisson-distributed for $n \to \infty$. Also, the number of permutations without any fixed points is equivalent to the rencontre problem. The latter is also solvable by the inclusion-exclusion principle, see [1, Chapter 1 exercises].

References

[1] H.-O. Georgii (2014): Stochastik. Eine Einführung.