From: jcbhrb@nic.cerf.net (Jacob Hirbawi)
Newsgroups: sci.math
Subject: Re: Combinatorical problem
Date: 13 Jan 1993 04:10:26 GMT
Organization: CERFnet Dial n' CERF Customer Group
Distribution: world
NNTP-Posting-Host: nic.cerf.net

In article <greil.726829446@guug.de> greil@guug.de (Anton Greil) writes:

> I'd like to append with a more general question:
> T(n) forms a generating system for S(n)  (for all n).
> How can the combinatorics of this generating system be characterized?
> Especially: does there exist a normal form of each generated element from
> S(n) over the base T(n) ?

I know of a form that has a number of nice features. (I'm not sure how it
relates to the two forms suggested by Vaughan Pratt but chances are good it's
a close relative). I'll look at permutations of degree 4 but all the results
are easily extended:

First let the transpositions T(4)={a1,b1,b2,c1,c2,c3} be defined by:

    a1 = (1,2),   b1 = (1,3),    c1 = (1,4),    ...
                  b2 = (2,3),    c2 = (2,4),
                                 c3 = (3,4),
then every permutation can be written uniquely as

     (ai^ri)(bj^rj)(ck^rk)  with     ri,rj,rk = 0 or 1
                            and i=1,j=1 or 2,k=1,2, or 3, ...

Inspite of the clumsy notation I hope the pattern is clear enough.
This is equivalent to expressing the numbers from 0 to n!-1 in the 
"factorial base" . I'll do the first 10 permutations, (according to an
obvious order):

  1234   <--> (000)  <--> (identity)
  2134   <--> (100)  <--> a1
  1324   <--> (010)  <--> b1
  3124   <--> (110)  <--> a1 b1
  2314   <--> (020)  <--> b2
  3214   <--> (120)  <--> a1 b2
  1243   <--> (001)  <--> c1
  2143   <--> (101)  <--> a1 c1

   p     <--> (C2,C3,C4)

The i'th coefficient, Ci, for permutation p can be calculated directly as the
  Ci = number of j < i  such that p(j) > p(i)

The sum of the the Ci's is odd or even according to the signature of p = -1,1.

> And - excuse please, yet more general - is there a connection to the general
> Moebius groups of the Euclidean spaces R_n, where each such Moebius transfor-
> mation can be generated by reflections, which are also elements of the
> (group-) order 2 ?

There is a connection which is either superficial or very deep (sometimes it's
hard to distinguish between the two ;-) ). These are also connected to 
semi-simple Lie algebras. Anyway Vaughan's decomposition of the symmetric
group into even and odd permutations extends very nicely to all reflection 
groups. The symmetric group, S(n), is in fact the "simplest" reflection group
and S(n+1) is associated with the (Weyl) reflection group of the Lie algebra
su(n). All reflection groups have a subgroup of index 2, called their
rotation group. The cosets of this subgroup divide the group into two subsets
satissfying exactly the conditions of the original problem posted by 
Matthew Newman:

>> For which n can one find a set B(n) such that for all p in S(n)
>> either p is in B(n), or p differs by exactly one transposition
>> from an element of B(n), and such that no two elements from B(n)
>> differ by exactly one transposition ?

Most of H.S.M Coxeter's books is a good reference on this as well as:
"Finite Reflection Groups" by L.C.Grove and C.T.Benson.   

Jacob Hirbawi
JcbHrb@CERF.net
Newsgroups: sci.math