home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 18070 < prev    next >
Encoding:
Internet Message Format  |  1993-01-12  |  3.4 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!howland.reston.ans.net!usc!news.cerf.net!nic.cerf.net!jcbhrb
  2. From: jcbhrb@nic.cerf.net (Jacob Hirbawi)
  3. Newsgroups: sci.math
  4. Subject: Re: Combinatorical problem
  5. Date: 13 Jan 1993 04:10:26 GMT
  6. Organization: CERFnet Dial n' CERF Customer Group
  7. Lines: 70
  8. Distribution: world
  9. Message-ID: <1j04niINNe98@news.cerf.net>
  10. NNTP-Posting-Host: nic.cerf.net
  11.  
  12. In article <greil.726829446@guug.de> greil@guug.de (Anton Greil) writes:
  13.  
  14. > I'd like to append with a more general question:
  15. > T(n) forms a generating system for S(n)  (for all n).
  16. > How can the combinatorics of this generating system be characterized?
  17. > Especially: does there exist a normal form of each generated element from
  18. > S(n) over the base T(n) ?
  19.  
  20. I know of a form that has a number of nice features. (I'm not sure how it
  21. relates to the two forms suggested by Vaughan Pratt but chances are good it's
  22. a close relative). I'll look at permutations of degree 4 but all the results
  23. are easily extended:
  24.  
  25. First let the transpositions T(4)={a1,b1,b2,c1,c2,c3} be defined by:
  26.  
  27.     a1 = (1,2),   b1 = (1,3),    c1 = (1,4),    ...
  28.                   b2 = (2,3),    c2 = (2,4),
  29.                                  c3 = (3,4),
  30. then every permutation can be written uniquely as
  31.  
  32.      (ai^ri)(bj^rj)(ck^rk)  with     ri,rj,rk = 0 or 1
  33.                             and i=1,j=1 or 2,k=1,2, or 3, ...
  34.  
  35. Inspite of the clumsy notation I hope the pattern is clear enough.
  36. This is equivalent to expressing the numbers from 0 to n!-1 in the 
  37. "factorial base" . I'll do the first 10 permutations, (according to an
  38. obvious order):
  39.  
  40.   1234   <--> (000)  <--> (identity)
  41.   2134   <--> (100)  <--> a1
  42.   1324   <--> (010)  <--> b1
  43.   3124   <--> (110)  <--> a1 b1
  44.   2314   <--> (020)  <--> b2
  45.   3214   <--> (120)  <--> a1 b2
  46.   1243   <--> (001)  <--> c1
  47.   2143   <--> (101)  <--> a1 c1
  48.  
  49.    p     <--> (C2,C3,C4)
  50.  
  51. The i'th coefficient, Ci, for permutation p can be calculated directly as the
  52.   Ci = number of j < i  such that p(j) > p(i)
  53.  
  54. The sum of the the Ci's is odd or even according to the signature of p = -1,1.
  55.  
  56. > And - excuse please, yet more general - is there a connection to the general
  57. > Moebius groups of the Euclidean spaces R_n, where each such Moebius transfor-
  58. > mation can be generated by reflections, which are also elements of the
  59. > (group-) order 2 ?
  60.  
  61. There is a connection which is either superficial or very deep (sometimes it's
  62. hard to distinguish between the two ;-) ). These are also connected to 
  63. semi-simple Lie algebras. Anyway Vaughan's decomposition of the symmetric
  64. group into even and odd permutations extends very nicely to all reflection 
  65. groups. The symmetric group, S(n), is in fact the "simplest" reflection group
  66. and S(n+1) is associated with the (Weyl) reflection group of the Lie algebra
  67. su(n). All reflection groups have a subgroup of index 2, called their
  68. rotation group. The cosets of this subgroup divide the group into two subsets
  69. satissfying exactly the conditions of the original problem posted by 
  70. Matthew Newman:
  71.  
  72. >> For which n can one find a set B(n) such that for all p in S(n)
  73. >> either p is in B(n), or p differs by exactly one transposition
  74. >> from an element of B(n), and such that no two elements from B(n)
  75. >> differ by exactly one transposition ?
  76.  
  77. Most of H.S.M Coxeter's books is a good reference on this as well as:
  78. "Finite Reflection Groups" by L.C.Grove and C.T.Benson.   
  79.  
  80. Jacob Hirbawi
  81. JcbHrb@CERF.net
  82.