Elementary Permutations without repetition

Question

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 01 '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 01 '18 at 19:47
Cycles are disjoint and transposition for each cycle only use those elements (https://en.wikipedia.org/wiki/Cycle_decomposition) — Quimey, Jun 01 '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 01 '18 at 21:31

score 2 · Accepted Answer · answered Aug 10 '18 at 05:36

2

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.

answered Aug 10 '18 at 05:36

joriki

238,052

Do you know how to get count of all the permutations with limited repetitions? Like count of all the variations between 0000000000 and 9999999999 with 5 repetitions in each variation? This is the question that I've asked: https://math.stackexchange.com/questions/4247472/permutations-with-global-limited-repetition-without-the-need-for-providing-digit – Eftekhari Sep 12 '21 at 17:21

Elementary Permutations without repetition

1 Answers1