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.

  • $\begingroup$ See if this question and answer combined with this one help. $\endgroup$ May 6, 2020 at 23:39
  • $\begingroup$ @BrianM.Scott: I think you linked to the same question twice... $\endgroup$ May 7, 2020 at 0:05
  • $\begingroup$ @ArturoMagidin: Thanks; you’re absolutely right. Here’s the correct second link. $\endgroup$ May 7, 2020 at 0:07
  • $\begingroup$ 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. $\endgroup$ May 7, 2020 at 0:09
  • $\begingroup$ @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! $\endgroup$ May 7, 2020 at 0:11


You must log in to answer this question.

Browse other questions tagged .