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.

Leave a Reply

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

You are commenting using your 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