Let $S_n$ be the symmetric group of $n$ letters, generated by elements $s_i$ for $ 1 \leq i \leq n -1$ with relations $s_is_{i+1}s_i = s_{i+1}s_is_{i+1} $ and $s_i,s_j$ commute if $|i-j| > 1$.

I would like to have an algorithm to get a list $w_1, \dots, w_{n!}$ which enumerates $S_n$ so that each $w_k$ can be expressed as a product in $s_1, \dots, s_{n-1}$.

For example for $S_3$ such a list is given by $1, s_1, s_2, s_1s_2, s_2s_1, s_1s_2s_1$. A list for $S_4$ or $S_5$ would be already nice.


For any $1\le i\le j\le n$, let $$ t^j_i=s_{j-1}s_{j-2}\cdots s_i, $$ with the convention that $t^i_i=1$. Any permutation in $S_n$ can be represented uniquely in the form $$ t^1_{a(1)}t^2_{a(2)}\dots t^n_{a(n)} $$ where $a(1),a(2),\dots,a(n)$ is a list of integers satisfying $1\le a(i)\le i$. Unpacking each $t^j_i$, you get an expression for each element of $S_n$ using the letters $s_i$.

The interpretation is that $t_{i}^j$ is a permutation which moves the item at slot $i$ to slot $j$, without disturbing any of the items above slot $j$.


If you have the list of words (representing functions) for the $n$ group,

$$\quad w_1, w_2, \dots, w_{n!}$$

you can mechanically generate the words for the $n+1$ group using two facts:

$\quad \text{Every (new) permutation has the form } w \circ \tau \text{ for a transposition } \tau = (k \; \; n+1)$

$\quad \text{Every transposition can be written as a product of adjacent transpositions}$

We will use this theory to get the words for $S_4$.

To organize the work, we created a google sheet; here are the $24$ elements in $S_4$ ($s_0$ is the identity):

enter image description here

We did not work on representing these words with the shortest length. For example, the word in cell $\text{C7}$ can obviously be reduced in length.

I am not aware of the theory that would give us an algorithm to do this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.