×

Computational Pólya theory. (English) Zbl 0833.20005

Rowlinson, Peter (ed.), Surveys in combinatorics, 1995. Proceedings of the 15th British combinatorial conference held in July 1995 at the University of Stirling, UK. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 218, 103-118 (1995).
Summary: 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,\dots,z_n)\) of \(G\) at the point \(z_1=\cdots=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 – are surveyed.
For the entire collection see [Zbl 0819.00016].

MSC:

20B40 Computational methods (permutation groups) (MSC2010)
20B30 Symmetric groups
05A19 Combinatorial identities, bijective combinatorics
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite