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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s