# How many lists are fixed by a pair of permutations?

Let $A$ be an alphabet of $N$ symbols and let a permutation act on a string of letters from $A$ in the obvious way.

If I ask how many strings $(i_1,...,i_n)\in A^n$ are fixed by a permutation $\pi$, the answer is, of course, $N^{c(\pi)}$, where $c(\pi)$ is the number of cycles of $\pi$.

But how many strings are fixed by two permutations $\pi_1,\pi_2$? That is, how many fixed points are there in $A^n$ with respect to the group generated by $\langle \pi_1,\pi_2\rangle$?

Or in more genrality, how many points in $A^n$ are fixed by a given subgroup $H\subset S_n$?

In your single permutation case you are splitting the $n$ positions into equivalence classes where two positions are in the same class if they are in the same cycle. You then require that all the characters in one equivalence class be the same, which is where the $N^{c(\pi)}$ comes from. With two permutations you again split into equivalence classes. The first permutation splits the positions into classes the same way as before. The second can then link up those classes into larger ones. Say $n=9$ and $\pi_1=(1234)(567)(8)(9)$ We have four classes and would have $N^4$ strings. If $\pi_2=(15)(2)(3)(4)(6)(78)(9)$ we now link the classes $(1234), (567),$ and $(8)$ so those positions have to be the same. We now have classes $(12345678)(9)$ and only $N^2$ acceptable strings.
• Yes, this is clear, but I was hoping for a solution which works for any $\pi_1,\pi_2$ without having to do the work manually. A formula involving, say, the number of cycles of $\pi_1^{-1}\pi_2$. In the example you gave, for instance, you get $N^2$; does this exponent 2 have any group-theoretical interpretation? – thedude Nov 10 '17 at 17:34
• I don't think you can get there with anything like $\pi_1^{-1}\pi_2$. Say they both have $(12)$ as part of the permutation. You need positions $1$ and $2$ to be the same but any product of an even number of terms will separate $1$ and $2$. I don't think the exponent $2$ has a group theoretical interpretation either because we could find permutations that do not cover the whole symmetric group on an equivalence class but still have the same equivalence classes. – Ross Millikan Nov 10 '17 at 17:44
The answer is the number of orbits of $H$ in the space $\{1,...,n\}$.
But this may not be practical. For instance, in the example given in Ross Millikan's answer, with $\pi_1=(1234)(567)(8)(9)$ and $\pi_2=(15)(2)(3)(4)(6)(78)(9)$, the group generated by $\pi_1,\pi_2$ has 2 orbits, but it has 40320 elements.