Outer Automorphisms of $S_n$

There are a lots of questions (and several good explanations) on understanding the non-trivial outer automorphism of $S_6$. What I haven't seen, though, is a good explanation of why there are no such outer automorphisms for $n\neq 6$. Wikipedia makes a passing mention of this fact here.

In particular, they have this cryptic claim:

For every symmetric group other than $S_6$, there is no other conjugacy class of elements of order 2 with the same number of elements as the class of transpositions.

This seems like the natural thing to prove, given the knowledge that you can construct an outer automorphism of $S_6$ which takes transpositions to products of three transpositions (i.e. things like $(12)\mapsto (12)(34)(56)$.) Also, the second reason Wikipedia gives doesn't feel very intuitive to me.

My question, then, is how does one justify the original (quoted) statement above?

Here is the naive computation of sizes of conjugacy classes: We need to show that when $n, k\neq 6,3$ $$\frac{n!}{2^k k! (n-2k)!}\neq\frac{n!}{2(n-2)!},$$which is equivalent to $$2^k k!(n-2k)!\neq 2(n-2)!$$

What I want to say is something like, if $n{-}2$ is bigger than $k$, then there is always some factor on the RHS that doesn't appear in the LHS (except when it is a power of two). Will this type of analysis get me anywhere, or is there a better way to think about this?

Yes, as you mention, $S_n$ has $n\choose2$ transpositions and the conjugacy class whose elements consist of $2\le k\le \frac n2$ disjoint transposition has $\frac{n!}{(n-2k)!2^kk!}$ elements. As you say, the condition that these numbers are the same is equivalent to $$\tag1 (n-2k)!2^{k-1}k!= (n-2)!$$

For $k=2$ this becomes $4(n-4)!=(n-2)!$ or equivalently $(n-2)(n-3)=4$, which has no integer solution.

For $k=3$, we obtain $ 24(n-6)!=(n-2)!$ or equivalently $(n-5)(n-4)(n-3)(n-2)=24$. This has integer solutions $n=6$ and $n=1$, the first leading to the exceptional situation with $S_6$, the other being invalid because it has $n<2k$.

For the rest of the argument, we may assume $k>3$. Then Bertrand's postulate states that there is a prime $p$ with $k<p<2k-2$. This $p$ does not divide $2^{k-1}k!$ but $n-2\ge2k-2$ implies that $p$ divides $(n-2)!$ so that we conclude that $p$ divides $(n-2k)!$ and finally that $p\le n-2k$. Rewrite (1) as $$\underbrace{2\cdot2\cdots 2}_{k-1}\cdot \underbrace{k\cdot (k-1)\cdots 2}_{k-1} = \underbrace{(n-2)(n-3)\cdots(n-2k+1)}_{2k-2}$$ Each of the $2k-2$ factors on the left is $\le k$, each of the $2k-2$ factors on the right is $>p>k$, hence equality cannot hold (as $2k-2\ne0$).

Just for interest, I'll treat the case $k >3$, trying to avoid the use of Bertrand's Postulate. Note that for $k >1$, $(n-2)!$ is divisible by $(n-2k)!(2k-2)!$. It suffices when $k > 3$ to prove that $2^{k-1}k! < (2k-2)!$, or equivalently that $(2k-2) \ldots (k+1) > 2^{k-1}$. There are $k-2$ terms in the left product, all at least $4.$ Also, we have $4^{k-2} > 2^{k-1}$ as $k >3.$

As an alternative to Hagen von Eitzen's answer for the $k>3$ case, we can avoid using Bertrand's postulate. Write the equation as \begin{align*} \underbrace{k(k-1)\cdots 2}_{k-1} \cdot \underbrace{2\cdot2\cdots 2}_{k-1} = \underbrace{(n-2)(n-3)\cdots(n-2k+1)}_{2k-2} \end{align*} and compare terms pairwise (i.e. compare $k$ and $n-2$, then $k-1$ and $n-3$, etc.). There are two cases: $2k=n$ and $2k<n$.

For the first case ($2k=n$), note that since $k > 3$, we have $n \geq 8$. Note that each term on the right is greater than or equal to its corresponding term on the left, except for the last term on the right which is 1. We want to show that the right side has another factor of two to show that it's greater than the left. Consider the last non-1 term of $k!$, 2, on the left side and its correspond term on the right side, $n-k=\frac{n}{2}$. Divide both of these terms by 2 (and rearrange them) to get \begin{align*} \underbrace{k(k-1)\cdots 3}_{k-2}\cdot\underbrace{2\cdot 2\cdots 2}_{k-1} = \underbrace{(n-2)(n-3)\cdots(n-k+1)}_{k-2}\cdot \underbrace{(n-k-1)(n-k-2)\cdots 3 \cdot 2 \cdot \frac{n}{4}}_{k-1} \end{align*} Since $n \geq 8$, we have $\frac{n}{4} \geq 2$, so that comparing terms pairwise, each term on the right is greater than or equal to its corresponding term on the left, and since $n-2>\frac{n}{2}=k$ for $n \geq 8$, the right side is strictly greater than the left.

For the second case ($2k<n$), all terms on the right are immediately greater than or equal to their corresponding terms on the left, and since once again $n-2>\frac{n}{2}>k$ for $n \geq 8$, the right hand side is strictly greater than the left.