Conference rusure::math

Theorem: 

The n! permutations of the integers 1..n can be arranged in a (circular)
sequence in which no two adjoining permutations have a common number, for
any n>3. 

Proof (by induction):

Given a solution for (n-1)!, we construct a solution for n!, as follows.

We replace each permutation (a,b,c,...,d,e) in the solution for (n-1)!,
with the following sequence of n permutations of the n values.

	(a,b,c,...,d,e,n)
	(n,a,b,c,...,d,e)
	(e,n,a,b,c,...,d)
	      ...
	(c,...,d,e,n,a,b)
	(a,b,c,...,d,n,e)

The first n-1 permutations in this group are cyclic permutations of
(a,b,c,...,d,e,n), and the last equals the first, with n and e interchanged.
This produces the desired solution for n, and is justified below.

Clearly, within each each group, there are no adjacent permutations with
equal numbers in any position (if n>3).

The permutations at the end of one group and the beginning of the next group
also satisfy this constraint.  Consider two adjacent permutations in the
(n-1)! solution:
	(a,b,c,...,d,e)
	(s,t,u,...,v,w).
The following permutations in the n! solution clearly satisfy the constraint:
	(a,b,c,...,d,n,e)
	(s,t,u,...,v,w,n).

Each of the n! permutations is represented exactly once, as can be seen by
considering, in turn, the (n-1)! permutations with n in the last position,
the (n-1)! with n in the first position, ..., and the (n-1)! permutations
with n in the penultimate position.  In each of these n cases, all (n-1)!
permutations of the other positions are represented, since all (n-1)!
permutations were present in the (n-1)! solution.

All that remains is to show a solution for n=4.  The following table
illustrates a solution, where each column represents a permutation.

	1431 3423 2412 3413 1421 2432
	2142 1341 3243 2342 3143 1241
	3214 2134 1324 1234 2314 3124
	4323 4212 4131 4121 4232 4313

Q.E.D.

Addendum:

Note that the solution for n=4 was generated by the above method from
the (invalid) sequence of permutations:

	132 312
	213 231
	321 123

In fact, there is no valid solution for n=3, since the adjacency constraint
requires that adjacent permutations be cyclic permutations of each other.
This divides the six permutations into two sets, where no permutation in
one set can be adjacent to any permutation in the other set.

Theorem: 
The n! permutations of the integers 1..n can be arranged in a sequence in
which no two adjoining permutations have any number in the same position,
for any n>3. 

Proof: (by Lynn Yarbrough, Lexington, MA)
Divide the permutations into (n-1)! groups as follows: The Head permutation
of each group begins with 1. The rest of the permutations in each group are
end-around rotations of the Head; e.g. the first group is 
	12..n
	2..n1
	..n12
	 .
	n12..
Clearly in each group no member has a number in the same position as any of
the others, so each group forms a reorderable subsequence of length n.
Rearrange each group so the third element above is in the nth, or Tail,
position. 

Now arrange the (n-1)! groups in sequence so that the Heads differ from
each other by the exchange of just two adjacent numbers of (2..n). (E.g.
using Jonhson's Algorithm.) Then the Tail permutations differ by the same
two numbers. Thus (if n> 3), the Tail of each group has no numbers in the
same position as the Head of the next group, since it is shifted two
places. Join the groups head to tail and the entire sequence has the
property that no two adjacent permutations have a number in the same
position. Q.e.d. 

The "Johnson's algorithm" that Lynn is referring to is given in

S. M. Johnson, Generation of permutations by adjacent transpositions,
	Math. Comp. 17(1963)282-285.