In a comment at the recent question What is the standard 2-generating set of the symmetric group good for?, it was remarked that the symmetric groups $S_n$ for $n\gt 2$, $n\neq 5,6,8$, can be generated by an element of order 2 and an element of order 3 (G. A. Miller, Bull. Amer. Math. Soc. 7 (1901), 424-426 doi:10.1090/S0002-9904-1901-00826-9). The remaining three nonabelian cases can of course be generated by a pair of elements, but these are cycles of length $5,6,8$ respectively. What is the best that can be done in these cases, and is there a conceptual reason why these are exceptional? (eg the presence of the nontrivial outer automorphism of $S_6$? Or some action on an exceptional combinatorial object?)
ADDED By 'conceptual' proof I mean something more like 'structural', or the analogue of what in combinatorics is a 'bijective proof'. There should be some actual construction for the generic case that clearly breaks down for the small cases, due to a lack of space. Compare for instance the deep understanding of what goes wrong with the sort of handle moves that happen in high-dimensional topology, when we go down to dimension 4, and then why the replacement there will not work in lower dimensions. Simply counting two sets and noticing they have the same number of elements isn't the sort of thing I want. Nor do I want a proof that just writes down a pair of generators and checks they work, but of course I do want to see said generators.
Best Answer
It is also possible to use the (exceptional) outer automorphism of order $2$ of $S_{6}$ to give an "explanation" of why $S_{6}$ is not $\{2,3\}$-generated, along the lines I used in comments for $S_{5}$ above. Take a $6$-cycle $\sigma \in S_{6}.$ Then $\sigma^{2}$ is a product of two disjoint three cycles and $\sigma^{3}$ is a product of three disjoint $2$-cycles. These clearly commute. Now take an outer automorphism $\tau$ of $S_{6}$ which sends products of two disjoint three cycles to three cycles. Then $\tau$ must also send products of three disjoint transpositions to transpositions, since $\tau(\sigma^{2})$ and $\tau(\sigma^{3})$ must commute.
Now suppose that $S_{6}$ is $\{2,3\}$-generated say $S_{6} = \langle \alpha, \beta : \alpha^{2} = \beta^{3} = 1 \rangle.$ Then we may apply $\tau$ if necessary, and assume that $\beta$ is a $3$-cycle. Then $\alpha$ is an odd permutation, so is either a transposition, or a product of three disjoint transpositions.
In the former case, we have a contradiction since there is a point fixed by both $\alpha$ and $\beta$. In the latter case, none of the transpositions in $\alpha$ can fix all points moved by $\beta$, for otherwise that transposition would be central in $\langle \alpha, \beta \rangle.$ It follows that $\alpha$ sends each point moved by $\beta$ to a point fixed by $\beta$ and conversely. It follows that $\beta$ and $\beta^{\alpha}$ commute. Now $\alpha$ normalizes the Abelian subgroup $\langle \beta, \beta^{\alpha}\rangle $, so that $\langle \alpha, \beta \rangle = \langle \alpha \rangle \langle \beta^{\alpha} ,\beta \rangle$ has order dividing $18$, a contradiction.
I do not know if there is an argument using the fact that $S_{8}$ is isomorphic to ${\rm GL}(4,2)\langle \gamma \rangle$, where $\gamma$ is the transpose inverse automorphism, to "explain" that $S_{8}$ is not $\{2,3\}$-generated.
Later edit: It would have been better perhaps to use the outer automorphism of $S_{6}$ to reduce to the case that $\alpha$ is a transposition,(in which case, generation requires that $\beta$ is a product of two disjoint $3$-cycles), and then note the general fact that when $n >1$, $S_{2n}$ is never generated by a transposition $\alpha$ and an element $\beta$ which is a product of two disjoint $n$-cycles. For if it were, we may conjugate the pair and assume that $\alpha = (12).$ If either of the $n$-cycles in $\beta$ were disjoint from $\alpha$, then that $n$-cycle would be central in $\langle \alpha, \beta \rangle = S_{2n}$, a contradiction. Hence both $n$-cycles of $\beta$ contain a point moved by $\alpha$.
We may conjugate $\beta$ by a permutation fixing both $1$ and $2$ and assume that $\beta = (1357 \ldots 2n-1)(2468 \ldots 2n)$ without disturbing the generation property. Then $\langle \alpha, \alpha^{\beta}, \ldots, \alpha^{\beta^{n-1}}\rangle$ = $\langle (12),(34), \ldots , (2n-1 2n) \rangle$ is Abelian and normal in $\langle \alpha, \beta \rangle = S_{2n},$ a contradiction.