I asked this question : Composition of permutation to generate all permutations earlier but I didn't phrase it well, here is my new question.

My question is a little bit different I'm looking for a set of permutation $\sigma_1$, ... $\sigma_p$ such that any composition (in this given order) $\sigma_1\circ\sigma_2\circ\cdots\circ\sigma_p\circ\sigma_1\circ\sigma_2\circ\cdots$ will generate all the permutation of a given list.

According to you answer I get that this sequence can be compose only of $\sigma_1=(1,2)$ and $\sigma_2=(1,2,...n)$, but this might not be optimal (because the sequence might be longer.)

Now my question is, what is the minimum sequence of $\sigma_1$ and $\sigma_p$ such that it generates all permutations of a set of $n$ element.

in my example with 1,2,3 above.

if I take $\sigma_1=(1,2)$ and $\sigma_2=(1,3)$

the sequence repeating sequence $\sigma_1\circ\sigma_2$ will generate all permutations :

id gives 1 2 3

$\sigma_1$ gives 2 1 3

$\sigma_1\circ\sigma_2$ gives 3 1 2

$\sigma_1\circ\sigma_2\circ\sigma_1$ gives 1 3 2

$\sigma_1\circ\sigma_2\circ\sigma_1\circ\sigma_2$ gives 2 3 1

$\sigma_1\circ\sigma_2\circ\sigma_1\circ\sigma_2\circ\sigma_1$ gives 3 2 1

I can phrase it this way :

Let $S_n$ be the symmetric group on $n$ elements. You are interested in subsets $\{a_0,a_1,\ldots,a_k,b\}$ where $a_0$ is the identity, such that for any $y∈S_n$, you can find $0≤j≤k$ and and natural number $M$ such that $y=bMaj$. And you want to find the minimum $k$. In other words, you are looking for the number of cosets in $S_n$ relative to the subgroup generated by $b$.

Thanks in advance.


1 Answer 1


If I understand you correctly, you are looking for elements $\sigma_1, \dots, \sigma_m$ of the symmetric group $S_n$ on $n$ elements such that the sequence $\sigma_1$, $\sigma_1\circ\sigma_2$, $\sigma_1\circ\sigma_2\circ\sigma_3, \dots, \sigma_1\circ\dots\circ\sigma_m$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots, \sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots$ lists every element of $S_n$ exactly once.

Defining $\tau := \sigma_1\circ\dots\circ\sigma_m$ this list can be written as $\tau^0\circ\sigma_1, \dots, \tau^0\circ\sigma_1\circ\dots\circ\sigma_{m-1}$, $\tau^1\circ\sigma_1, \dots, \tau^1\circ\sigma_1\circ\dots\circ\sigma_{m-1}$, $\tau^2\circ\sigma_1, \dots, \tau^2\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \dots$.

Written like this, you see that if $\tau$ has the order $k$ (also called period), the sequence repeats itself after $\dots, \tau^{k-1}\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \tau^k$. So if you pick an element $\tau$ whose order is maximal in $S_n$, you will get $m$ minimal, as you always have

$$m = \frac{|S_n|}{k} = \frac{n!}{k}.$$

Now pick elements $\tau_1, \dots, \tau_m$ from the different right cosets of the (cyclic) group $\langle \tau \rangle$ generated by $\tau$, where without loss of generality you may take $\tau_m = \tau$. Then define $\sigma_1 := \tau_1$ and $\sigma_i := \tau_{i-1}^{-1}\circ\tau_i$ for $i = 2,\dots, m$.

It is then not to hard to prove that this sequence $\sigma_1, \dots, \sigma_m$ fulfills your conditions and is as short as possible if the order of $\tau$ is chosen maximal among the elements of $S_n$. As lhf commented on my answer posted on your original question, the maximal possible order of elements of $S_n$ is given by Landau's function, which roughly grows like $\mathrm{e}^{\sqrt{n\log{n}}}$.


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.