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 is for all . The existence of a function such that the expectation is for will follow easily. Now let’s get started on the main event.
Whenever we mention the cycles of an element in we always mean the cycles in its unique cycle decomposition. We being with a definition:
Definition 1: Let . Then we define , where returns the number of fixed points in .
For , . That is, there is one element of with fixed points, three elements with fixed point, and two elements with no fixed points. In particular, is always a monic polynomial of degree . Now we may let be a function on so that we may attach a generating function to it. In particular, we have the following identity:
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 it’s easy to see that the coefficient of the th term is precisely . Armed with this identity, we can prove the first of our aims.
Proposition 1: The average number of fixed points in a permutation on letters is .
proof: Consider the identity
Now notice that if we take the derivative of with respect to and then set , we have the average number of fixed points across all permutations in . So setting gives
Equating coefficients gives .
Here’s a quick example. We can list the permutations of as . 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 , the same as the size of , so the expectation is .
To prove our second result, we’re now going to need a generalization of . This generalization will let us count the number of -cycles across elements in for .
Definition 2: Let with . Then , where is the number of -cycles in .
Notice that in particular, . The previous identity and Proposition 1 can be generalized for and the proofs are just slight alterations. The analogous identity is
The generalization of Proposition 1 for 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 -cycles appearing in elements of , namely , is given by whenever . In particular, .
Looking back at our example, it can be seen that if we choose any cycle of length in with , the number of those cycles appearing in elements of is given by . Now lets prove the existence of .
Proposition 3: Let be given by , where and elements in divide . Then after the map.
proof: Let such that divide . Now consider the functions for each . By our second proposition, these functions tell us there are -cycles, -cycles, etc., appearing in elements of . But these are all the cycles which return the identity after the map since divide . So the number of fixed points after the map is . It follows that .
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!