How can two elements of group $S_4$ generate the whole group $S_4$? I struggle to prove that two elements of non-cyclic group $S_4$ can generate the whole group.
The task is to find at least two such couples too.
I suppose that this is somehow connected with the order of the permutation. I know that the highest order of permutation (I take a permutation as an element of group $S_4$) is $4$. But how can be this applied when I want to work with $2$ elements? 
I know that another approach could be to take any two elements and try to generate the group..
Thank you very much.
 A: Since any permutation can be written as a product of cycles, and any cycle can be written as a product of transpositions by using the rule
$$(c_1c_2....c_k) = (c_1c_k)(c_1c_{k-1}) \cdots (c_1c_2)$$
We can immediately conclude that $S_n$ is generated by all of the transpositions. Our next step is to 
show that we can actually restrict our generating set to the transpositions of 
the form $(i \ \ i+1$). These are sometimes called simple transpositions. That is,
$\\$
$$S_n=\big<(12)(23)(34)\cdots (n-1,n) \big> \\ $$
Since any permutation can be written as a product of cycles, and we've already shown that any cycle
can be written as a product of 2-cycles, all we need to show is that any 2-cyle can be written as a 
product of the simple cycles $(e.g. \ (23),(56),etc.)$. For example,
.
$$ \\ (14) = (12)(23)(34)(23)(12) \\ $$ The proof is as follows:
Lemma: Any transposition $(ab)$ can be written as a product of simple transpositions.
$ \\ $
$\underline{\text{Proof}}$: 
We induct on $k = b-a$. $($ for instance the $k=3$ cycles would be $(14),(25),(36)$ etc. 
Basis step: For $k = 1$,  $ \quad b-a = 1 \implies (a\ b) = (a \ a+1) $ which is already in the correct form.
$ \\ $
Induction step: Suppose that any transposition of the form $(ab)$ where $b-a = k$
can be written as
a product of simple cycles and let $(ab)$ be a transposition with $b-a = k+1$.
Note that $$(a \ b) = (a \ a+1) (a+1 \ b) (a \ a+1)$$.
Since  $b-(a+1) = b-a-1 = k$ the induction hypothesis tells us that $(a+1 \ \ b)$ is a product of
simple transpositions and hence so is $(ab)$. This is easiest to see with an example. 
Lets use  $(14)$ again. We write $(14) = (12)(24)(12)$.
Now we apply the same trick to $(24)$ and write $(24) = (23)(34)(23)$. 
Substituting this in we have $$(14) = (12)(24)(12)=(12)(23)(34)(23)(12)$$
$ \\ $
So now we have succeeded in showing that $S_n$ is generated by the simple transpositions. Hence to
show that $S_n = \big<(12)(12 \dots n)\big>$, we now only need to show that each of the simple transpositions 
can be obtained from $(12) \text{ and } (12\cdots n)$. Clearly the $(12)$ case is already taken care of. 
$ \\ $
Let $\sigma = (12\cdots n)$. Note that $\sigma (12) \sigma^{-1} = (\sigma(1),\sigma(2)) = (23)$ Reasoning inductively, we see that 
$ \\ $
$$\sigma^k (12) \sigma^{-k} = (k+1 \ k+2) $$ 
and in this way we obtain all of the simple transpositions and therefore all of $S_n$
$ \\ $
Note: This result can actually be strengthened to $S_n = \big<(ab)(12\cdots n)\big>$ whenever
$gcd(b-a,n) = 1$. Furthermore, ANY transposition and ANY p-cycle will generate $S_p$ if p is prime.
EDIT:
Here I'm letting $\sigma = (12 \cdots n)$. Its a general theorem that for any permutation, call it $\tau$ to avoid confusion, that $\tau (c_1c_2\cdots c_k)\tau^{-1} = (\tau(c_1) \tau(c_2) \cdots \tau(c_k))$. If you haven't learned this you can just visually inspect it one at a time. For instance $(1234)(12)(4321) = (23)$., then $(1234)(23)(4321) = (34)$. So now we have shown that its possible to get $(12),(23),(34)$, from $(12),(1234)$, that its then possible to get any 2-cycle from $(12),(23),(34)$,that is possible to get any cycle from all the 2-cycles, and that its then possible to get any permutation from all the cycles.
A: Hint: $S_3 = \langle (12), (123) \rangle$. Can you generalize this to $S_4$? Can you generalize this to $S_n$?
A: I'll give another way to think about it.  Using a transposition and an n-cycle, you can generate all the transpositions.  You finish by applying the bubble sort algorithm to generate all the possible permutations of $S_n$.
