# Elementary Permutations without repetition

A permutation $\sigma$ of a set $\{1,2,...,k\}$ is a bijective function mapping this set onto it self. Denote the set of all permutations of this set by $S_{k}$.

An elementary permutation $e_{i}$ of $S_{k}$ is a permutation that satisfies $e_{i}(j)=j$ if $j\notin\{i,i+1\}$, $e_{i}(i)=i+1$ and $e_{i}(i+1)=i$. That is, $e_{i}$ change $i$ with $i+1$ and preserves another numbers.

We know that every permutation $\sigma$ can be written by a composition of elementary permutations. But I'm thinking in something that I didn't saw at any book: Every permutation $\sigma$ can be written by a composition of elementary permutations with no repetition? By 'no repetition' I mean that a elementary permutation $e_{i}$ doesn't appear more than one time in the composition for $\sigma$

• I think the answer to your question is yes. It is enough to do it for cycles and for those is quite easy. – Quimey Jun 1 '18 at 19:45
• I doubt it is enough to consider the cycle case, since by composing cycles you might get repetitions. – Hw Chu Jun 1 '18 at 19:47
• Did you try to do this for $S_3$? – Tobias Kildetoft Jun 1 '18 at 19:50
• Cycles are disjoint and transposition for each cycle only use those elements (en.wikipedia.org/wiki/Cycle_decomposition) – Quimey Jun 1 '18 at 19:50
• At $S_{3}$ I found the permutation $(\sigma (1),\sigma (2),\sigma (3))=(3,2,1)$. There's no way to express $\sigma$ in terms of elementary permutations without repetition. Is there some rule about that? – Mateus Rocha Jun 1 '18 at 21:31

As discussed in the comments, the permutation $(13)\in S_3$ cannot be represented as a product of neighbour exchanges without either of the two available exchanges being used twice.
More generally, there are $n-1$ neighbour exchanges, and we can form at most $\sum_{k=0}^{n-1}k!$ different products from them. For $n\gt2$, this is less than $n!$ (which you can prove by induction), so we can't generate all $n!$ permutations with these products.