Computational Pólya Theory

Mark Jerrum

Abstract: A permutation group G of degree n has a natural induced action on words of length n over a finite alphabet Sigma, in which the image xg of x under permutation g \in G is obtained by permuting the positions of symbols in x according to g. The key result in ``Pólya theory'' is that the number of orbits of this action is given by an evaluation of the cycle-index polynomial P_G(z_1,...,z_n) of G at the point z_1=...=z_n= |Sigma|. In many cases it is possible to count the number of essentially distinct instances of a combinatorial structure of a given size by evaluating the cycle-index polynomial of an appropriate symmetry group G.

We address the question ``to what extent can Pólya theory be mechanised?'' There are compelling complexity-theoretic reasons for believing that there is no efficient, uniform procedure for computing the cycle-index polynomial exactly, but less is known about approximate evaluation, say to within a specified relative error. The known results --- positive and negative --- will be surveyed.

LFCS report ECS-LFCS-95-317, January 1995.

Previous | Index | Next