Show that \(S_n\) is generated by each of the following sets:
Transpositions \(\{(a\,b) \mid 1 \le a < b \le n\}\).
Adjacent transpositions \(\{(i\,i+1) \mid 1 \le i \le n-1\}\).
\(\{(1\,2), (1\,2\,\dots\,n)\}\) for \(n\ge 2\).
\(\{(1\,2), (2\,3\,\dots\,n)\}\) for \(n\ge 3\).
\(\{(a\,b), (1\,2\,\dots\,n)\}\) where \(1\le a<b\le n\) iff \(\gcd(b-a, n) = 1\).
Any arbitrary transposition and any arbitrary \(p\)-cycle in \(S_p\) (\(p\) prime).
Solution
Every permutation is a product of transpositions, so all transpositions generate \(S_n\).
Let \(s_i=(i\ i+1)\). For \(i<j\), \[ (i\ j)=s_i s_{i+1}\cdots s_{j-2}s_{j-1}s_{j-2}\cdots s_i, \] so the adjacent transpositions generate every transposition and hence \(S_n\).
Let \(c=(1\ 2\ \dots\ n)\). Then \[ c^k(1\ 2)c^{-k}=(1+k\ 2+k) \] (indices modulo \(n\)), so \(\langle(1\ 2),c\rangle\) contains all adjacent transpositions. Hence it is \(S_n\).
Let \(d=(2\ 3\ \dots\ n)\). Then \[ d^k(1\ 2)d^{-k}=(1\ d^k(2)), \] so \(\langle(1\ 2),d\rangle\) contains every star transposition \((1\ j)\). Since \[ (i\ j)=(1\ i)(1\ j)(1\ i), \] these generate \(S_n\).
Now fix \(\tau=(a\ b)\) and \(c=(1\ 2\ \dots\ n)\), and put \(d=b-a\) modulo \(n\). The conjugates \[ c^k\tau c^{-k} \] are the transpositions joining \(x\) to \(x+d\) in \(\ZZ/n\ZZ\). These transpositions generate the full symmetric group on each connected component of the graph with edges \(\{x,x+d\}\).
If \(\gcd(d,n)=1\), the graph is connected, so the conjugates of \(\tau\) already generate \(S_n\).
If \(g=\gcd(d,n)>1\), the graph has \(g\) components, namely the cosets modulo \(g\). The cycle \(c\) permutes these components cyclically, so \(\langle\tau,c\rangle\) preserves this nontrivial block system. Hence it is a proper subgroup of \(S_n\). Therefore \[ \langle(a\ b),(1\ 2\ \dots\ n)\rangle=S_n \iff \gcd(b-a,n)=1. \]
Finally, if \(p\) is prime, relabel any \(p\)-cycle as \((1\ 2\ \dots\ p)\). For any transposition \((a\ b)\) we have \(1\le b-a<p\), hence \[ \gcd(b-a,p)=1. \] By the criterion \(\langle(a\ b),(1\ 2\ \dots\ n)\rangle=S_n\iff\gcd(b-a,n)=1\) with \(n=p\), any transposition together with any \(p\)-cycle generates \(S_p\).