All generating sets of $S_3$? I am trying to find all generating sets of $S_3$, is there a theorem which states how many sets I should have?
I know for example $(12)$ and $(123)$ is one such generating set however my question is 'how do I find all generating sets without having to compute them with brute force?' as of course, this will be lengthy.
 A: I am not aware of any general theorem for this task. However, since $S_3$ is not cyclic, every set that generates it must have at least two distinct elements, both of which are distinct from the identity element $e$. That doesn't leave you with many choices. In fact, any subset $S$ of $S_3\setminus\{e\}$ with at least two distinct elements generates $S_3$, with one exception: that's when $S=\bigl\{(1\ \ 2\ \ 3),(1\ \ 3\ \ 2)\bigr\}$; this set generates the subgroup $\bigl\{e,(1\ \ 2\ \ 3),(1\ \ 3\ \ 2)\bigr\}$.
A: Since the order of $S_3$ is $6$, you can do the following: let $X$ be a subset. If $X$ contains an element of order $3$ and an element of order $2$, then it contains the subgroup they generate and so, by Lagrange's theorem, it generates $S_3$. 
If $X$ does not contain an element of order $3$, then it contains only transpositions. If it contains only one transposition, then clearly $X$ generates a cyclic group, and $S_3$ is not cyclic. So it contains at least two. Now note that $(12)(23) = (123)$ (and similarly the product of any two distinct transpositions has order $3$), so again $X$ generates $S_3$.
If $X$ does not contain an element of order $2$, then it contains only element of order $3$. But there are two of those, and they are multiples of each other, so in this case $X$ can only generate $C_3$.
In the end, $X$ generates $S_3$ if and only if $X$ contains at least one transposition and a distinct nontrivial element.
In general, you can say that transpositions generate a symmetric group, or that a $n$-cycle and a transposition generate $S_n$, but the aim is more oriented towards finding a generating set, instead of all.
There are, however, probabilistic results that for particular classes of groups $G$ tell you what is the probability that any two, three, $n$ random elements generate $G$.
A: The group $S_3$ consist of the unit element $1$, three transpositions $(12), (13), (23)$ and two 3-cycles $(123),(132)$.
The transpositions are reflections of an equilateral triangle and the 3-cycles are rotations by 120 degrees each.
The subgroups of $S_3$ are the trivial subgroups, the subgroups of order 2 each of which given by one of the transpositions, and one subgroup of order 3, given by the 3-cycles.
Note that two reflections provide a rotation. 
This information should be enough to construct all generating sets.
A: Let me try to collect a few things written in the comments. I will argue that the only non-generating set is the one comprising the two elements of order $3$. Observe, first, that if $S \subset S_3$ contains at least one element of order $2$ and at least one element of order $3$ then $|S_3| = 2 \cdot 3 \mid |\langle S \rangle|$, thus $\langle S \rangle = S_3$.
If a subset $S \subset S_3$ contains at least three elements then either it must contain at least one element of order $3$ and at least one element of order $2$, so $\langle S \rangle = S_3$ in that case, or the three transpositions. For the latter case see further down.
Therefore, the problem reduces to showing that the only non-generating set with two elements is the one comprising the two elements of order $3$. By the previous argument, an element of order $2$ and an element of order $3$ generate $S_3$. So the matter is merely to show that any two transpositions generate $S_3$. The product of any two transpositions in $S_3$, however, results in an element of order $3$ and we are done.
To answer the counting part of the question: any subset of $S_3 \setminus \{\mathrm{id}\}$ is a generating set except $\{(123), (132) \}$. In total, we thus have $2^5 -1$ generating sets. If instead you want minimal generating sets then you are looking at ${5 \choose 2}-1 = 9$.
P.S. The working assumption here is that only non-trivial elements can contribute as generators. If we include the trivial element then the count needs correction.
