Looking at permutations I came up with the following question:
Can you find a permutation $S$ of a set of $n$ elements such that by composing this permutation $n!$ times you will describe all the possible permutations of this set.
i.e, all permutation of a given set can be expressed as a composition of this permutation.
But it's not possible:
Proof: (not sure it's the most straightforward proof)
let $S$ be a permutation, it can be decomposed into disjoint cycles. Finding a permutation S that verify the above constraint would mean that the least common multiple of these cycles is n!.
So at least decompose $S$ into one cycle of $n$ elements, one cycle of $n-1$ etc.
But it's impossible since the cycle are disjoints.
Now, may be instead of looking for a single permutation to generate all permutations, I could look at a composition of permutation that will describe all the permutations of a set.
For example, I would like to find $S_1$ and $S_2$ such that $S_1$, $S_1\circ S_2$, $S_1\circ S_2\circ S_1$ etc. describe all the permutations.
With a set of $3$ elements it's pretty easy to find such $S_1$ and $S_2$:
S1 = 1 2 3 //permute first and second element 2 1 3 S2 = 1 2 3 //permute first and third element 3 2 1
By composing S1, S1°S2 etc... I get
1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1
My question is, what is the minimum number of permutations for a set of n element that will describe all the set. Is there an easy way to get these permutations?
Thanks in advance.
thanks for your answers I rephrased the question on another question : Question on permutation