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 S1 and S2 such that S1, S1°S2, S1°S2°S1 etc... describe all the permutations.
With a set of 3 elements it's pretty easy to find such S1 and S2:
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