# Proof of a simple permutation problem

Consider a set $$S = \{1,2,\ldots,n\}$$, use $$\Sigma$$ to denote all permutations of the set $$S$$. The ordered set $$\sigma \in \Sigma$$ is a permutation of $$S$$.

Define operators $$G_i$$ for $$i= 1,\ldots, n-1$$, such that $$G_i(\sigma)$$ swaps the the $$i$$-th number and ($$i$$+1)-th number in the ordered set $$\sigma$$.

$$\textbf{Problem}:$$ Let the ordered set $$\sigma_0$$ be $$\{1,2,\ldots,n\}$$, show that any permutation $$\sigma \in \Sigma$$ can be obtained via applying some sequence of $$G_i$$ to the set $$\sigma_0$$.

This is something very simple I encountered in my research. I can think of proving this using the idea of "bubble sort". However, as I an new to the field of combinatorics/group theory, I do not know a good system of notations to present the proof. I searched online and saw the Cauchy's two line notation, but still don't know how to apply it properly. Any help or suggestion regarding the notations will be greatly appreciated.

• See if this question and answer combined with this one help. May 6, 2020 at 23:39
• @BrianM.Scott: I think you linked to the same question twice... May 7, 2020 at 0:05
• @ArturoMagidin: Thanks; you’re absolutely right. Here’s the correct second link. May 7, 2020 at 0:07
• The question amounts to showing that the symmetric group $S_n$ can be generated by the transpositions $(1,2)$, $(2,3),\ldots,(n-1,n)$. Searching for that is sure to produce any number of nice proofs. May 7, 2020 at 0:09
• @BrianM.Scott Thank you for the comment. Now I see how to use the notations to define the operators $G_i$. But How can I show that any permutation can be obtained through applying a sequence of $G_i = (i,i+1)$? Thank you again! May 7, 2020 at 0:11