Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

So I think it's possible to create an infinite sequence of transpositions T = { ti, i ≥ 2 } satisfying ∀ i[2,n!]

  • a,b[1,n] s.t. ti = (a b)
  • n!|(j - i)tj = ti

such that if you consider the sequence of permutations Pn = { pi,n, i ∈ [1,n!] } defined by

  • p1,n is the identity permutation
  • pi+1,n = pi,n ti+1

that Pn contains every permutation of n elements exactly once.


For example, if T starts with

{ (1 2), (1 3), (1 2), (1 3), (1 2), (1 4),
  (1 2), (1 3), (1 2), (1 3), (1 2), (2 4),
  (1 2), (1 3), (1 2), (1 3), (1 2), (3 4),
  (1 2), (1 3), (1 2), (1 3), (1 2), ....

then P4 is given by

{ (1 2 3 4), (2 1 3 4), (3 1 2 4), (1 3 2 4), (2 3 1 4), (3 2 1 4),
  (4 2 1 3), (2 4 1 3), (1 4 2 3), (4 1 2 3), (2 1 4 3), (1 2 4 3),
  (1 3 4 2), (3 1 4 2), (4 1 3 2), (1 4 3 2), (3 4 1 2), (4 3 1 2),
  (4 3 2 1), (3 4 2 1), (2 4 3 1), (4 2 3 1), (3 2 4 1), (2 3 4 1) }

and P4 contains every permutation of 4 elements exactly once.


What I'd like to find is a constructive proof for the existence of T. I'm sure I'm retreading old ground here, I just don't seem to be searching for the right terms to turn up what I'm looking for.

share|improve this question
    
    
@Richard Stanley: Thanks! The link you gave was broken, but it was enough for me to find Wikipedia's page on the Steinhaus–Johnson–Trotter algorithm. If you'd like to upgrade your comment to an answer, I'd be happy to accept it. –  user1596 Mar 17 '12 at 22:43
    
O.k., I will upgrade my comment. I am glad it helped. –  Richard Stanley Mar 17 '12 at 23:55

1 Answer 1

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.