# Composition of permutation to generate all permutations

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 ?

EDIT:

thanks for your answers I rephrased the question on another question : Question on permutation

-
The question is too long. Perhaps leave just the final part with a brief paragraph about the current answers? Or ask a separate question? I'm not sure which is best though. See meta.math.stackexchange.com/questions/2814/… –  lhf Aug 24 '11 at 12:39
You should ask a new question. However I look at it, your original question (as phrased) was answered perfectly by huitseeker. Your revised question can be phrased as follows: 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 \in S_n$, you can find $0\leq j\leq k$ and and natural number $M$ such that $y = b^Ma_j$. 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$. –  Willie Wong Aug 24 '11 at 14:15
It seems you have two extremes. You can go with lhf's two generators $\{(12),(123...n)\}$ and perhaps have longer compositions, or use all of $S_n$ to get the shortest compositions (length 1). There are many others in between. You choose. :-) –  robjohn Aug 24 '11 at 14:24
...and with that, by thinking about this, you reduce the question to one about the maximum order of an element of the symmetric group $S_n$. There is no known formula as of ten years ago, though it has asymptotics like $\exp \sqrt{n \log n}$. –  Willie Wong Aug 24 '11 at 14:29
Thanks I created a new question, you might want to migrate your answer there ? –  Ricky Bobby Aug 24 '11 at 14:40

(Disclaimer: I'm writing a somewhat detailed answer, since I noticed this came from SO (and the vocabulary in which the question was formulated). Apologies if it's too long-winded for some.)

If I understand correctly, you have a set S of size n, and you want to look at the set of all possible permutations P(S) of that set.¹

That P(S) is the symmetric group of order n, usually noted $S_n$. You want to find a (minimal) generating set of $S_n$.

A generating set of $S_n$ is the set of all transpositions $σ_{i,j}$, for 1 ≤ i,j ≤ n, where $σ_{i,j}$ is the permutation that swaps i and j and leaves all the other elements unchanged ².

To prove that, you want to show that any permutation can be written as a "product" (composition) of transpositions. You'll find numerous proofs of that around, let me just say the gist of it is to proceed by induction on n. Then, given a permutation p of (n+1) elements, you find a product of transpositions q such that (q ∘ p) (n+1) = (n+1) : then (q∘p) is a permutation of n elements, which by induction hypothesis can be written as a product of transpositions, and from that, you can write p itself as a product of transpositions.

That generating set is not minimal: for example, you easily can reduce it to adjacent transpositions (those transpositions of the form (i,i+1), for 1 ≤ i < n), and still have a generating set.

Nonetheless, this allows us to notice that to prove a set of permutations Π is a generating set of $S_n$, it is enough to prove that any adjacent transposition can be written as a product of permutations in Π.

Let us now take a cycle of maximal length, say (1,2,3,...,n), and a single adjacent transposition, say (1,2). You'll notice that for any 0 ≤ i < (n-1)³:

$(1,2,3,...,n)^i(1,2)(1,2,3,...,n)^{-i}$ = (i+1,i+2)

This is the same reasoning we have applied in the link above to show transpositions can be expressed as a product of adjacent transpositions: you "shift" all elements using the cycle, apply your transposition, and then "de-shift" everything.

So, all adjacent transpositions, and therefore all permutations, can be expressed as a product of a cycle of maximal length and a single adjacent transposition. I'll leave showing that generating set is minimal as an exercise.

¹: You'll notice the contents of S are irrelevant, so that we can denote the elements of S as {1,...,n}, representing the actual elements by their indexation.

²: In cycle notation, this is also noted (i,j). We'll keep using cycle notation henceforth.

³: Here, the exponentiation denotes the iterated composition: $p^i$ means applying i times permutation p.

-
thanks a lot for your answer, the question is a little bit different, I clarified it. –  Ricky Bobby Aug 24 '11 at 12:04

The symmetric group on $n$ symbols is not cyclic when $n>2$ (it's not even abelian). Hence it cannot be generated by a single permutation. However, it can always be generated by two permutations, a transposition $(12)$ and a cycle $(123\ldots n)$.

-
thanks a lot for your answer, the question is a little bit different, I clarified it. –  Ricky Bobby Aug 24 '11 at 12:04

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$. (If you want to know this order, ask another question ;-)).

-
Landau's function is the maximum order of an element in $S_n$ –  lhf Aug 24 '11 at 13:52