$(12)$ and $(123\dots n)$ are generators of $S_n$

Solution 1:

Let $c = (1, 2, \dotsc, n)$. We see that \begin{align*} c (1, 2) c^{-1} &= (2, 3) \\ c (2, 3) c^{-1} &= (3, 4) \\ &\vdots \\ c (n-2, n-1) c^{-1} &= (n-1, n), \end{align*} so that $(i, i+1) \in \langle (1, 2), c \rangle$ for all $1 \leq i \leq n-1$. Next, we have \begin{align*} (2, 3) (1, 2) (2, 3)^{-1} &= (1, 3) \\ (3, 4) (1, 3) (3, 4)^{-1} &= (1, 4) \\ &\vdots \\ (n-1, n) (1, n-1) (n-1, n)^{-1} &= (1, n), \end{align*} so that $(1, i) \in \langle (1, 2), c \rangle$ for all $1 \leq i \leq n$. Choose any $1 \leq i < j \leq n$, then $$ (i, j) = (1, i) (1, j) (1, i)^{-1} \in \langle (1, 2), c \rangle. $$ Therefore, $\langle (1, 2), c \rangle$ contains all transpositions. Hence, $\langle (1, 2), c \rangle = S_n$.

Solution 2:

First, we use Induction to prove that: $\forall k \in \{1,2,3...n\}: (k \ k+1) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$.

Base Case:

$ (1 \ 2) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$

Induction Step:

Suppose: $ (k \ k+1) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$

Then: $(1 \ 2 \ 3 \ 4\ ..n)(k \ k+1)(1 \ 2 \ 3 \ 4\ ..n)^{-1}= (k+1 \ k+2)$

Further, we will prove that: $ \forall k \in \{1,2,3...n\} : (1 \ k) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$.

Base Case:

$ (1 \ 2) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$

Induction Step:

Suppose: $(1 \ k) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$

Then: $(k \ k +1) ( 1\ k) (k \ k+1)^{-1}=(1 \ k+1)$

Finally we show that: $\forall a ,b \in \{1,2,3...n\} : (a \ b) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$.

Let $a,b \in \{1,2,3...n\}$ be arbitrary.

Then: $(1 \ a)(1 \ b)(1 \ a) = (a \ b)$

Thus: $( a \ b) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$

Conclusion
All transpositions can be generated by $ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$ that means that $S_n$ is generated by $ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$