perm filename POLAY.WRU[FOO,LMM] blob sn#099905 filedate 1974-05-01 generic text, type C, neo UTF8
C00001 00001
C00002 00002	This project  is  to modify  an existing  INTERLISP  program due  to
C00005 ENDMK
This project  is  to modify  an existing  INTERLISP  program; due  to
incompatiblities and features  not available in ILISP you may find it
necessary to  rewrite the whole  thing.   The general  problem is  to
compute the number of different colorings of a set of N objects under
symmetry  group G ⊂ S↓n, coloring n1 of  the objects with color 1, n2
of them with color 2, ..., nk of them with color k.

(n1+n2+n3 ...)=N.

 By application of Polya enumeration formula, the number of colorings
is the coefficient  of x1↑n1*x2↑n2*...*xk↑nk in the cycle index of G.
(the cycle index  of a group is  a polynomial expressed  as a sum  of
products of sums of powers of the xi↑s).The program you will be given
will work given the cycle index in a suitable representation. Project
will consist of:

 (1) adding a preprocessor which will compute the cycle index given a
group in permutation list form.

  (2) improving the algorithm  by not attempting  expansions of terms
which will not contribute to the final sum.

 (3)  {harder} rewriting /  writing algorithm so  that it  counts the
number of  double cosets (in Sn) given two groups  G and H (the above
problem is a special case of this). Alternatively, expand it  to work
on some other applications of general Polya enumeration.