# Using Polya's enumeration theorem for explicit generation of instances

I have a simple application of Polya's enumeration theorem to counting nonisomorphic pentago boards with a given number of stones. In terms of the theorem, the color generating function is $f(x) = 1+x+y$ corresponding to empty, black, or white, there are $6 \times 6 = 36$ beads, and the group is $Z_4^4 \rtimes D_4$ of size 2048. This all works well.

Next I want to explicit generate a set of representative instances, one from each isomorphism class, without generating all instances and reducing. Is there an analogue of Polya's theorem that would assist in explicit enumeration of instances?

If necessary I can do this by manually unwrapping the structure of my particular group, but am curious if there is a more abstract technique applicable to arbitrary groups.

-
A related but more powerful version would be to construct an efficient random access enumeration of nonisomorphic instances. I.e., an efficient function $f:Z_{|S|} \to S$, where S is a set of representatives of equivalence classes. – Geoffrey Irving Apr 15 '12 at 18:44
There is some discussion of this question in Chapter 4 of the book Combinatorics for Computer Science by Gill Williamson. On page 144 it says "Pólya enumeration theory is not generally a good tool for actually listing the system of representatives ..." – Richard Stanley Apr 15 '12 at 18:59
My guess is that such a coding function is possible for any group which can be fully decomposed into small pieces in some sense. It certainly isn't for all groups, including $S_n$, and the fact that $S_n$ contains a huge simple group might explain why. – Geoffrey Irving Apr 15 '12 at 19:08
Richard: Thanks, I was afraid of that. I'll take a look at Williamson's book. I am curious of there's a large class of groups for which efficient random access enumeration functions can be defined, but I suppose that's a separate question. – Geoffrey Irving Apr 15 '12 at 19:14

[Added:] Thinking about this a bit more: There are about 5000 equivalence classes of sub-board; make them all anyhow. Then you just need to select four of these in inequivalent ways according to the action of $D_8$. The inequivalent boards with four inequivalent sub-boards are the tuples $(A,B,C,D)$, $(A,C,D,B)$ and $(A,D,B,C)$ with $A\lt B\lt C\lt D$; i.e., coset representatives of $D_8$ in $S_4$. Then there more types but much smaller counts where some of the sub-boards are equivalent.