## 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
*x*^{g} 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