Generating permutations How to prove that it is possible to generate all the permutations of  $n$ elements from any permutation of $n$ elements using a sequence of swap operations where swap is allowed only between the $\displaystyle 1^{st}$ position and any other position.  
 A: Assuming that permutations act from left (as usual), e.g. for the cycle $(123)=(1\mapsto 2\mapsto 3\mapsto 1)$, we can write $(123)2=3$.
By plugging in all elements $1,2,..,n,\ a,b$ to both sides of the equations below, verify them:


*

*$(1234...n)=(12)(23)(34)...((n-1)n)$

*$(ab)=(1a)(1b)(1a)$ if $a,b\ne 1$.

A: You can do this by induction on $n$. For $n\leq1$ there is nothing to prove. Now assuming $n>1$ consider the final value $\pi_n$ of the permutation you want to achieve. If $\pi_n=n$ one just needs to permute the first $n-1$ elements and the induction hypothesis suffices. So assume $\pi_n=a<n$. If $a>1$ start by swapping $1$ with $a$ (if not just skip this step), then swap the first element (which now holds the value $a$) with element $n$; this achieve a permutation $\sigma$ with $\sigma_n=a$. So $\sigma$ differs from the desired permutation $\pi$ by a permutation of the first $n-1$ elements. As before, the induction hypothesis provides such a permutation, so it suffices to follow the two mentioned swap operations with that permutation.
