# Presentation: UMRS Spring 2018

Here’s another written version of a presentation I gave in 2018 at UMN’s USMR (undergraduate mathematics research seminar). I spoke about using generating functions to compute the expectancy of fixed points in permutations. Some of the proofs in this talk are technical, so I’ve decided to cut them and only present the critical ones. After reading, if you’re curious about the technical details feel free to send me an email here and I’d be happy to send a copy to you! As a final note, some familiarity with generating functions is assumed.

#### UMRS 2-20-2018 Presentation

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. I’ll leave that for you to play around with if you feel like it. That concludes the presentation, thanks for reading!