2
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • $\begingroup$ Oh, sorry! I was going to post this in MSE, ended up posting it in MO by mistake! Apologies... $\endgroup$
    – thedude
    Commented Oct 24, 2017 at 23:36
  • 2
    $\begingroup$ The answer should be $N^c$, where $c$ is the number of equivalence classes on the set $\left\{1,2,\ldots,2n\right\}$ with respect to the equivalence relation which relates each $k$ both with $\pi\left(k\right)$ and with $2n+1-k$. $\endgroup$
    – darij grinberg
    Commented Oct 25, 2017 at 3:13
  • 1
    $\begingroup$ Equivalently the answer is $N^c$, where $c$ is the number of orbits of the group generated by $\pi$ and the involution mapping $k$ to $2n+1-k$. In this formulation it is clear that for almost all $\pi$ the answer is $N$. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Oct 25, 2017 at 9:34
  • 1
    $\begingroup$ @WhatsUp: Almost all means that as $n\rightarrow\infty$, the proportion of $\pi\in S_{2n}$ having this property tends to 1. To see this note first that for an orbit of size $\ell$ there are $(2n-\ell)!\ell!$ permutation leaving this orbit invariant. If $\sigma$ is the involution mapping $k$ to $2n-k+1$, then the number of $\pi\in S_{2n}$, such that $\langle\pi, \sigma\rangle$ is not transitive, is at most $\sum_{A\subseteq [2n]} (2n-|A|)!|A|!$, where $\sum_A$ runs over all sets satisfying $k\in A\Rightarrow 2n-k+1\in A$. The number of such sets of size $2\ell$ is $\binom{n}{\ell}$. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Oct 25, 2017 at 16:43
  • 1
    $\begingroup$ Hence the number of such $\pi$ is bounded by $\sum_\ell\binom{n}{\ell}(2n-2\ell)!(2\ell)! = (2n)!\sum_\ell\binom{n}{\ell}\binom{2n}{2\ell}^{-1}$. Comparing the sum to a geometric series we get that this expression is $(2n)!(\frac{2}{n}+\mathcal{O}(n^{-2})$. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Oct 25, 2017 at 16:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .