Permutations that commute with a given transposition

Question

I have to count how many permutations $\sigma \in S_n$ commute with a transposition $(i, j), i \neq j$. My guess is that any $\sigma$ that doesn't contain $(i, j) $ in its cycle decomposition works, but I don't know how to count those nor if these are all permutations that satisfy the condition

Answer 1

$\newcommand{\Span}[1]{\left\langle #1 \right\rangle}$$\newcommand{\Size}[1]{\left\lvert #1 \right\rvert}$First of all, if you just want to compute the order of the centraliser, you may use the fact that all transpositions are conjugate in $S_{n}$.

Assuming $n \ge 2$, there are $$ \frac{n (n - 1)}{2} = \binom{n}{2} $$ transpositions, so that by orbit-stabiliser the centraliser of the involution, say, $\tau = (n-1, n)$ must have order $$ \dfrac{\Size{S_{n}}}{\dbinom{n}{2}} = \dfrac{n!}{\left(\dfrac{n (n - 1)}{2}\right)} = 2 \cdot (n-2)! $$

Now it is not difficult to see which permutations commute with $\tau$.

The factor $(n-2)!$ in the order is given by the permutations that do not involve $n-1$ and $n$, and these form a group isomorphic to $S_{n-2}$. The factor $2$ is given by the group generated by $\tau$, which clearly commutes with itself.

Thus the centraliser of $\tau$ in $S_{n}$ is $$ \Span{\tau} \times S_{n-2}. $$

Answer 2

Let $\sigma=(a_1\,a_2\,\dots\,a_k)$ be a cycle and $\tau$ any permutation; then $$ \tau\sigma\tau^{-1}=(\tau(a_1)\,\tau(a_2)\,\dots\,\tau(a_k)) $$ (composition is “right to left”).

Moreover, if $\sigma_1=(a_1\,a_2\,\dots\,a_k)$ and $\sigma_2=(b_1\,b_2\,\dots\,b_l)$, then $\tau\sigma_1\tau^{-1}$ and $\tau\sigma_2\tau^{-1}$ are disjoint as well.

Thus there are two cases when $\tau=(1\,2)$ is a transposition and $\sigma$ is a permutation such that $\tau\sigma=\sigma\tau$, that is, $\tau\sigma\tau^{-1}=\sigma$ (it is not restrictive to assume that $\tau=(1\,2)$, up to a renaming):

1. $\sigma$ leaves $1$ and $2$ fixed, or
2. one of the cycles of $\sigma$ is $(1\,2)$.

Indeed, if $1$ or $2$ appear in a cycle for $\sigma$ having length $>2$, we have $\tau\sigma\tau^{-1}\ne\sigma$. The same if a cycle $(1\,i)$ (with $i\ne2$) or $(2\,i)$ (with $i\ne1$) appears in $\sigma$.

If we remove the $(1\,2)$ cycle from the ones in the second case, we get all that fall in the first case, and conversely. Since the ones for the first case are exactly the permutations on $\{3,4,\dots,n\}$, the number you're looking for is $$ 2\cdot(n-2)! $$