Permutations that commute with a given transposition

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

$$\newcommand{\Span}{\left\langle #1 \right\rangle}\newcommand{\Size}{\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}.$$

• I don't really know much group theory, but I understand that there are $(n-2)!$ permutations that commute with that transposition? – user69503 Oct 28 '18 at 16:38
• It's $2 \cdot (n-2)!$, the centraliser of $\tau$ in $S_{n}$ is just the set (a subgroup, really) of the elements of $S_{n}$ that commute with $\tau$. – Andreas Caranti Oct 28 '18 at 16:40
• Thank you very much! I think I get it now. – user69503 Oct 28 '18 at 16:44

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)!$$