Prove that the symmetric group \(S_n\) is generated by each of the following sets of permutations: (1) All transpositions: \(\{(i \, j) \mid 1 \le i < j \le n\}\). (2) Adjacent transpositions: \(\{(1 \, 2), (2 \, 3), \dots, (n-1 \, n)\}\). (3) A single transposition and a full cycle: \(\{(1 \, 2), (1 \, 2 \, 3 \, \dots \, n)\}\). (4) \(\{(1 \, 2), (2 \, 3 \, \dots \, n)\}\). (5) \(\{(a \, b), (1 \, 2 \, \dots \, n)\}\) where \(1 \le a < b \le n\), if and only if \(\gcd(b - a, n) = 1\). (6) For a prime \(p\), any arbitrary transposition \((a \, b)\) and any arbitrary \(p\)-cycle \(\sigma \in S_p\).
Solution
Every permutation is a product of transpositions, so all transpositions generate \(S_n\).
Every transposition can be expressed using adjacent transpositions; for \(i<j\), \[ (i\ j)=s_{j-1}\cdots s_{i+1}s_i s_{i+1}\cdots s_{j-1}, \qquad s_k=(k\ k+1). \] Hence the adjacent transpositions generate \(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\).
If \(r=(2\ 3\ \dots\ n)\), then \[ (1\ 2)r=(1\ 2\ \dots\ n), \] so part (3) applies.
Put \(d=b-a\) modulo \(n\) and \(c=(1\ 2\ \dots\ n)\). The conjugates \[ c^k(a\ b)c^{-k} \] are exactly the transpositions joining \(x\) to \(x+d\) in \(\mathbb Z/n\mathbb Z\). The graph with these edges is connected exactly when \[ \gcd(d,n)=1. \] If it is connected, its edge transpositions generate \(S_n\), so \(\langle(a\ b),c\rangle=S_n\).
If \(g=\gcd(d,n)>1\), the vertices split into the \(g\) residue classes modulo \(g\). All conjugate transpositions preserve each class, while \(c\) cyclically permutes these classes. Hence the generated group preserves this nontrivial block system and is imprimitive; it cannot be \(S_n\). Therefore \[ \langle(a\ b),c\rangle=S_n \iff \gcd(b-a,n)=1. \]
- If \(p\) is prime, conjugate/relabel any \(p\)-cycle to \((1\ 2\ \dots\ p)\). Any transposition then has difference \(d\) with \(1\le d<p\), hence \(\gcd(d,p)=1\). Part (5) gives \(S_p\).