perm filename POLAY.WRU[FOO,LMM] blob sn#099905 filedate 1974-05-01 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00002 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 This project is to modify an existing INTERLISP program due to C00005 ENDMK C⊗; 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.