Presentation: Expectancy of Fixed Point Permutations Using Generating Functions

Here’s a script for a presentation I gave in 2018 at UMN’s Undergraduate Mathematics Research Seminar (UMRS). I spoke about using generating functions to compute the expectancy of fixed points in permutations.

Expectancy of Fixed Point Permutations Using Generating Functions

Given a permutation, the amount of fixed points it has is, loosely-speaking, a measure of how close that permutation is to the identity. Here we discuss a method of showing that the expectation of fixed points for $\sigma \in S_{n}$ is $1$ for all $n \in \mathbb{N}$. The existence of a function $\varphi_{m}:S_{n} \rightarrow S_{n}$ such that the expectation is $m$ for $1 \le m \le n$ will follow easily. Now let’s get started on the main event.

Whenever we mention the cycles of an element in $S_{n}$ we always mean the cycles in its unique cycle decomposition. We being with a definition:

Definition 1: Let $n \in \mathbb{N}$. Then we define $C_{n}(x) = \sum_{\sigma \in S_{n}}x^{fp(\sigma)}$, where $fp(\sigma)$ returns the number of fixed points in $\sigma$.

For $n = 3$, $C_{3}(x) = \sum_{\sigma \in S_{3}}x^{fp(\sigma)} = x^{3}+3x+2$. That is, there is one element of $S_{3}$ with $3$ fixed points, three elements with $1$ fixed point, and two elements with no fixed points. In particular, $C_{n}(x)$ is always a monic polynomial of degree $n$. Now we may let $C_{n}(x)$ be a function on $\mathbb{N}$ so that we may attach a generating function to it. In particular, we have the following identity:

$\sum_{n \in \mathbb{N}}C_{n}(x)\frac{t^n}{n!} = \exp\left\{tx+\sum_{n \ge 2}\frac{t^n}{n}\right\}$.

The proof of this identity uses the exponential formula for generating functions, so coming up with the generating function on the right-hand side is core of the proof. Yet, checking the identity holds is not hard. By expanding the right-hand side and collecting terms in powers of $t^{n}/n!$ it’s easy to see that the coefficient of the $(t^{n}/n!)$th term is precisely $C_{n}(x)$. Armed with this identity, we can prove the first of our aims.

Proposition 1: The average number of fixed points in a permutation on $n$ letters is $1$.

proof: Consider the identity

$\sum_{n \in \mathbb{N}}C_{n}(x)\frac{t^{n}}{n!} = \exp\left\{tx+\sum_{n \ge 2}\frac{t^{n}}{n}\right\}$.

Now notice that if we take the derivative of $C_{n}(x)/n!$ with respect to $x$ and then set $x = 1$, we have the average number of fixed points across all permutations in $S_{n}$. So setting $E(n) = C'_{n}(1)/n!$ gives

\begin{aligned} D_{x}\left(\sum_{n \in \mathbb{N}}C_{n}(x)\frac{t^{n}}{n!}\right) &= D_{x}\left(\exp\left\{tx+\sum_{n \ge 2}\frac{t^{n}}{n}\right\}\right) \\ \implies \sum_{n \in \mathbb{N}}\frac{C'_{n}(x)}{n!}t^{n} &= t \cdot \exp\left\{tx+\sum_{n \ge 2}\frac{t^{n}}{n}\right\} \\ \implies \sum_{n \in \mathbb{N}}E(n)t^{n} &= t \cdot \exp\left\{t+\sum_{n \ge 2}\frac{t^{n}}{n}\right\} \\ &= t \cdot e^{\log{\frac{1}{1-t}}} \\ &= \frac{t}{1-t} \\ &= \sum_{n \in \mathbb{N}}t^{n} \end{aligned}

Equating coefficients gives $E(n) = 1$.

Here’s a quick example. We can list the permutations of $S_{3}$ as $(123), (132), (1)(23), (2)(13), (3)(12), (1)(2)(3)$. Here we’ve included writing fixed points so they will be easier to count. After a quick glance, the number of total fixed points is $6$, the same as the size of $S_{3}$, so the expectation is $1$.

To prove our second result, we’re now going to need a generalization of $C_{n}(x)$. This generalization will let us count the number of $m$-cycles across elements in $S_{n}$ for $1 \le m \le n$.

Definition 2: Let $n,m \in \mathbb{N}$ with $1 \le m \le n$. Then $C_{n,m}(x) = \sum_{\sigma \in S_{n}}x^{c_{m}(\sigma)}$, where $c_{m}(\sigma)$ is the number of $m$-cycles in $\sigma$.

Notice that in particular, $C_{n,1}(x) = C_{n}(x)$. The previous identity and Proposition 1 can be generalized for $C_{n,m}(x)$ and the proofs are just slight alterations. The analogous identity is

$\sum_{n \in \mathbb{N}}C_{n,m}(x)\frac{t^n}{n!} = \exp\left\{\frac{t^{m}}{m!}x+\sum_{n \ne m}\frac{t^n}{n}\right\}$.

The generalization of Proposition 1 for $C_{n,m}(x)$ is the following, and is left to you to try and prove (you may assume the above identity is true):

Proposition 2: The number of $m$-cycles appearing in elements of $S_{n}$, namely $M_{n}$, is given by $|S_{n}|/m$ whenever $1 \le m \le n$. In particular, $|S_{n}| = m \cdot M_{n}$.

Looking back at our example, it can be seen that if we choose any cycle of length $m$ in $S_{3}$ with $1 \le m \le 3$, the number of those cycles appearing in elements of $S_{3}$ is given by $|S_{3}|/m$. Now lets prove the existence of $\varphi_{m}$.

Proposition 3: Let $\varphi_{m}:S_{n} \rightarrow S_{n}$ be given by $\varphi(\sigma) = \sigma^{k}$, where $k \in \mathbb{N}$ and $m$ elements in $\{1,2,\ldots,n\}$ divide $k$. Then $E(n) = m$ after the map.

proof: Let $p_{1},p_{2},\ldots,p_{m} \in \{1,2,\ldots,n\}$ such that $p_{1},p_{2},\ldots,p_{m}$ divide $k$. Now consider the functions $C_{p_{i},n}(x) = \sum_{\sigma \in S_{n}}x^{c_{p_{i}}(\sigma)}$ for each $i \in \{1,2,\ldots,m\}$. By our second proposition, these functions tell us there are $|S_{n}|/p_{1}$ $p_{1}$-cycles, $|S_{n}|/p_{2}$ $p_{2}$-cycles, etc., appearing in elements of $S_{n}$. But these are all the cycles which return the identity after the map since $p_{1},p_{2},\ldots,p_{m}$ divide $k$. So the number of fixed points after the map is $\sum_{i = 1}^{m}\frac{|S_{n}|}{p_{i}}p_{i} = m|S_{n}|$. It follows that $E(n) = m$.

Examples for Proposition 3 are easy to cook up, like the previous ones, and quite fun to check.