= Solution
Use rightmost-first composition of <permutations>, and let
$$
a=(1\,2\,\cdots\,n),\qquad b=(n-1\,n-2\,\cdots\,1).
$$
For $n\ge2$, direct evaluation gives $ab=(1\,n)$. Conjugating this <transposition> by powers of $a$ yields the <transpositions> between consecutive letters around the cycle, including $(1\,2),(2\,3),\ldots,(n-1\,n)$.
Put $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+1}s_i.
$$
Thus the adjacent <transpositions> generate every <transposition>, and <permutation cycle> decomposition shows that <transpositions> generate the <symmetric group>. Therefore $\langle a,b\rangle=S_n$.
For the final lower bound, associate a <graph> to a family of <transpositions>: its vertices are the letters and its edges are the swapped pairs. Every generator preserves every connected component, so generation of $S_n$ requires that <graph> to be connected. A connected <graph> on $n$ vertices needs at least $n-1$ edges: adding an edge can reduce the number of components by at most one, starting from $n$ isolated vertices. The adjacent <transpositions> supply exactly $n-1$ edges. Equivalently, <transpositions on a connected graph generate the symmetric group>. Hence
$$
\boxed{\text{The least number of transpositions generating }S_n\text{ is }n-1.}
$$
Back to article page
