Let $A$ be an alphabet of $N$ symbols. Let $S_n$ be the group of permutations of $n$ symbols. A permutation acts on a string of letters from $A$ in the obvious way.

If I ask, given a permutation $\pi\in S_n$, how many strings $(i_1,...,i_n)\in A^n$ does it fix?, the answer is, of course, $N^{c(\pi)}$, where $c(\pi)$ is the number of cycles of $\pi$.

I want to ask a different question: given a permutation $\pi\in S_{2n}$, how many *symmetric* strings $(i_n,...,i_1,i_1,...,i_n)$ does it fix?

6more comments