### Random Permutations (Part 1)

#### Posted by John Baez

I’m going to solve some problems on random permutations in my combinatorics class, to illustrate some of the ideas on species and generating functions, but also to bring in some ideas from complex analysis.

In all these problems we choose permutations randomly from $S_n$, with each permutation having probability $1/n!$ of being chosen.

I’ll start with one that’s easy, given the stuff I’ve already explained in class.

**Puzzle 1.** What is the probability that a randomly chosen permutation of an $n$-element set has exactly $k$ fixed points? What does this probability converge to as $n \to \infty$?

In homework the students already computed the probability that a randomly chosen permutation of an $n$-element set has *no* fixed points. A permutation with no fixed points is called a derangement, and the number of derangements of an $n$-element set is called the subfactorial $!\!n$.

Using the inclusion-exclusion principle, the number of derangements of $\{1,\dots, n\}$ is the number of permutations of this set, minus the number of permutations that fix the point $1$, minus the number that fix the point $2$,… minus the number that fix the point $n$, plus the number that fix the points $1$ and $2$, plus the number that fix the points $1$ and $3$,… minus the number that fix the points $1, 2$ and $3$,… and so on.

In short:

$!n = n! \; -\; \binom{n}{1} (n-1)! + \binom{n}{2} (n-2)! - \cdots + (-1)^n \binom{n}{n} (n-n)!$

We can simplify this to

$!\!n = n! \, \left(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!} \right)$

Thus, the probability that a permutation of an $n$-element set has no fixed points is

$\frac{!\!n}{n!} = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!}$

and this approaches $1/e$ as $n \to \infty$. So cool.

Now, what about $k$ fixed points? To choose a permutation of an $n$-element set with $k$ fixed points, we need to choose $k$ points and then choose a derangement of the remaining $(n-k)$-element set. There are

$\binom{n}{k} \, !(n-k)$

ways to do this. Thus, the probability that a permutation of an $n$-element set has $k$ fixed points is

$\binom{n}{k} \; \frac{!\!(n-k)}{n!}$

which can be written more charmingly as

$\frac{1}{k!} \; \frac{!\!(n-k)}{(n-k)!}$

We have seen that as $n \to \infty$ we have

$\frac{!\!(n-k)}{(n-k)!} \to \frac{1}{e}$

Thus, as $n \to \infty$, the probability that a permutation of an $n$-element set has $k$ fixed points approaches

$\frac{1}{e \, k!}$

Note that these probabilities sum to $1$, as they must.

**Puzzle 2.** In the $n \to \infty$ limit, what is the expected number of fixed points of a permutation of an $n$-element set?

You might naively think it would be infinite, but remember as we increase the size of our set we decrease the probability that any point gets mapped to itself.

We know that in the $n \to \infty$ limit the probability of there being $k$ fixed points is

$\frac{1}{e \, k!}$

so in this limit, the expected number of fixed points is

$\sum_{k \ge 0} k \frac{1}{k! e} = \frac{1}{e} \sum_{k \ge 1} \frac{1}{(k-1)!} = 1$

Exactly one!

You might also wonder what’s the expected number of fixed points for an arbitrary finite $n$, but I’ll leave that to you.

## Re: Random Permutations (Part 1)

Is it clear why the limit as $n \to \infty$ of the expected number of fixed points of a permutation on $n$ elements is the same as $\sum_{k = 0}^\infty P_k k$, where $P_k$ is the limit as $n \to \infty$ of the probability of a permutation on $n$ elements having exactly $k$ fixed points? This seems like the sort of interchange-of-limits argument with which one must take some care.