Polya Enumeration: Generate Configurations off of Cycle Index

Question

I have a 3×3 grid.

$$\begin{array}{|c|c|c|}
\hline
1 & 2 & 3\\
\hline
4 & 5 & 6\\
\hline
7 & 8 & 9\\
\hline
\end{array}$$

The symmetries are the 4 rotations (0, 90, 180, 270), and 4 reflections (top/down, left/right, 2 diagonals). Dihedral 4 group, I believe.

The cycle index becomes:

$$
\frac{1}{8}[x^9_1 + 2x^1_1x^2_4 + x^1_1x^4_2+4x^3_1x^3_2]
$$

I want to colour the grid two colours, so I expand with Polya's Enumeration Theorem:
$$
\frac{1}{8}[(a+b)^9 + 2(a+b)(a^4+b^4)^2 + (a+b)(a^2+b^2)^4+4(a+b)^3(a^2+b^2)^3]
$$
Expanding just the first term $(a+b)^9 $
has terms
$$
a^9 + 9 a^8 b + 36 a^7 b^2 + 84 a^6 b^3 + 126 a^5 b^4 + 126 a^4 b^5 + 84 a^3 b^6 + 36 a^2 b^7 + 9 a b^8 + b^9
$$

In this expanded form, the $126a^5b^4$ means that I have around 126 configurations with 5 of colour $a$ and 4 of colour $b$ (probably less since I didn't divide).

Is there a way to enumerate these 126 unique configurations, other than brute force?

I would like to extend this to something like a 6×6 grid, but these coefficients will only grow larger.

Answer 1

Pólya enumeration is good for counting (finding the number of), but not generally for listing.

But yes, there are efficient methods for also listing configurations subject to group action, other than brute force. See this MO question for suggestions such as orderly generation. (In one of the comments Richard Stanley quotes Gill Williamson: "Pólya enumeration theory is not generally a good tool for actually listing the system of representatives ...").

As to your present problem: SageMath and its IntegerVectorsModPermutationGroup package can do it, and you may want to study how it does it (i.e. study the algorithm). At any rate, having a computational solution gives you something to check your manual solutions against (either the counts or the listings).

Representing color $a$ as $0$ and $b$ as $1$, here are the configurations with only one $b$:

sage: G=PermutationGroup([[(1,3,9,7),(2,6,8,4)],[(1,3),(7,9),(4,6)]])
sage: len(G)
8
sage: G.is_isomorphic(DihedralGroup(4))
True
sage: IV1=IntegerVectorsModPermutationGroup(G, sum=1, max_part=1)
sage: list(IV1)
[[1, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 0, 0, 0]]

You may want to check (1) whether this makes sense [hint: I think it does; just think of the possibilities where that one $b$ could go in the grid], (2) whether the count from your Pólya enumeration matches this (does it give $3$).

For four $b$'s we get $23$ configurations.

sage: IV4=IntegerVectorsModPermutationGroup(G, sum=4, max_part=1)
sage: list(IV4)
[[1, 1, 1, 1, 0, 0, 0, 0, 0],
 [1, 1, 1, 0, 1, 0, 0, 0, 0],
 [1, 1, 1, 0, 0, 0, 1, 0, 0],
 [1, 1, 1, 0, 0, 0, 0, 1, 0],
 [1, 1, 0, 1, 1, 0, 0, 0, 0],
 [1, 1, 0, 1, 0, 1, 0, 0, 0],
 [1, 1, 0, 1, 0, 0, 0, 0, 1],
 [1, 1, 0, 0, 1, 1, 0, 0, 0],
 [1, 1, 0, 0, 1, 0, 1, 0, 0],
 [1, 1, 0, 0, 1, 0, 0, 1, 0],
 [1, 1, 0, 0, 1, 0, 0, 0, 1],
 [1, 1, 0, 0, 0, 1, 1, 0, 0],
 [1, 1, 0, 0, 0, 1, 0, 1, 0],
 [1, 1, 0, 0, 0, 1, 0, 0, 1],
 [1, 1, 0, 0, 0, 0, 1, 1, 0],
 [1, 1, 0, 0, 0, 0, 1, 0, 1],
 [1, 1, 0, 0, 0, 0, 0, 1, 1],
 [1, 0, 1, 0, 1, 0, 1, 0, 0],
 [1, 0, 1, 0, 1, 0, 0, 1, 0],
 [1, 0, 1, 0, 0, 0, 1, 0, 1],
 [1, 0, 0, 0, 1, 1, 0, 1, 0],
 [0, 1, 0, 1, 1, 1, 0, 0, 0],
 [0, 1, 0, 1, 0, 1, 0, 1, 0]]
sage: len(_)
23