Transpositions of adjacent elements generate the symmetric group on a finite set

From Groupprops
Jump to: navigation, search

Statement

Let S be a totally ordered finite set. Then, the set of Transposition (?)s between adjacent elements in the total ordering of S generates the Symmetric group (?) on S.

Note that any totally ordered set can be identified with the set \{1,2,3,\dots,n\} with the usual integer ordering, so the above can be rephrased as: the set of transpositions of the form (i,i+1) generate the symmetric group on \{1,2,3,\dots,n\}.

It turns out that this generating set is both Sims-reduced and Jerrum-reduced.

Related facts

Proof

The bubble sort proof

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]