# Today I Learned

Some of the things I've learned every day since Oct 10, 2016

## 108: Generating Set for the Symmetric Group

There are many possible choices of a generating set for $S_n$, the symmetric group. However, one particularly simple one is the set

$\{(0, 1, 2, \dots, n-1), (0, 1)\}$

where $0, 1, 2, \dots, n-1$ is an ordering of the elements being permutated by the elements of $S_n$, $(0, 1, 2, \dots, n-1)$ is the permutation ‘shifting’ all these elements to their successor, and $(0, 1)$ is the permutation swapping the first 2 of these.

I won’t provide a formal proof here as it’s a little tedious, but you can easily convince yourself that every permutation of these $n$ elements is a combination of these 2 permutations, because alternating between them in succession allows you to move any of the $n$ elements to an arbitrary position in the ordering.