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.

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,


EDIT:

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

share|improve this question
1  
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
1  
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
1  
...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

3 Answers 3

up vote 4 down vote accepted

(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.

share|improve this answer
    
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)$.

share|improve this answer
    
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 ;-)).

share|improve this answer
    
Landau's function is the maximum order of an element in $S_n$ –  lhf Aug 24 '11 at 13:52

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.