How many automorphisms of $S_n$ take transpositions into transpositions? I need to show that an automorphism of $S_n$ which takes transpositions to transpositions is an inner automorphism.
I thought it could be done by showing that such automorphisms form a subgroups $H\le Aut(S_n)$, that $Inn(S_n)\subset H$ and that they have the same number of elements. The number of inner automorphisms is $n!$ because $S_n$ has a trivial center (at least when it is not abelian) and therefore is isomorphic to $Inn(S_n)$. However I have no idea how I could count the number of elements in $H$.
Is there a way to do it, or should I change the approach altogether?
Thank you.
 A: Kannappan Sampath's suggestion can be completed as follows.
Let $f$ be an automorphism of $S_n$ with the property that it maps all transpositions to transpositions. So $f(1k)=(a_kb_k)$ for all $k=2,3,\ldots,n$, where $a_k\neq b_k$ are elements of the set $\{1,2,\ldots,n\}$. As the permutations $(12)$ and $(13)$ don't commute, their images $(a_2b_2)$ and $(a_3b_3)$ don't commute either. This means that the intersection $\{a_3,b_3\}\cap\{a_2,b_2\}$ is a singleton. Without loss of generality we can assume that $a_2=a_3=a$.
Next I claim that for all $k>3$ we also have $a\in\{a_k,b_k\}$. Assume contrariwise that for some $k>3$ we have $a_k\neq a\neq b_k$. Because $(1k)$ does not commute with $(12)$, we must have $b_2\in\{a_k,b_k\}$. Similarly, because $(1k)$ does not commute with $(13)$ either, we must also have $b_3\in\{a_k,b_k\}$, so $(a_kb_k)=(b_2b_3)$. But this is a contradiction, because then
$$
f(23)=f((13)(12)(13))=(ab_3)(ab_2)(ab_3)=(b_2b_3)=f(1k)
$$
violating the fact that $f$ is injective.
Thus all the transpositions $(a_kb_k)$ move the element $a$, and w.l.o.g. we can assume that $a_k=a$ for all $k$. All the integers $b_k\neq a$, and they must also be distinct, so the mapping $\sigma: 1\mapsto a, k\mapsto b_k$ is in $S_n$. We have shown that $f$ agrees with the inner automorphism $x\mapsto \sigma x\sigma^{-1}$ on all the $(n-1)$ generators $x=(1k),k=2,3,\ldots,n,$ of the group $S_n$, so the claim follows.
A: I think there is an easier way of looking at this (now edited to get the argument correct - and also simpler, thanks to Jyrki's comment). An inner automorphism of $S_n$ is equivalent to a permutation of the underlying set on which $S_n$ acts. Let's choose our generators to be a permutation $a=(1 2)$ and the n-cycle $b=(1 2 3 ... n)$.
Then we know that the automorphism sends $a$ to another transposition $a'$. 
Consider the cycle decomposition of $b'$, the image of $b$. The two objects permuted by $a'$ must be adjacent within the same cycle in $b'$ (else $b'^{-1}a'b'$ will be found to be a transposition moving different objects from $a'$ and will commute with it, and this is not true for $a, b$). 
Suppose the objects moved by $a'$ are adjacent in a cycle of length $m&ltn$ in $b'$. Then $b'^m$ will commute with $a'$ (it will not move the objects moved by $a'$). This is not true for $a, b$, so we must have $m=n$ i.e. $b'$ is an $n$-cycle with the elements moved by $a'$ adjacent. Since this is the same cycle pattern as for $a, b$ there will be a permutation of the underlying objects which does the job, and this is the required inner automorphism.
