Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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}}}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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