I want to find all possible colorings for a given number of colors $C$ on a board with cells $M \cdot N$ (both are even numbers). The board has periodic boundry conditions, so shifting the pattern to the left, right, up and down is considered to be the same pattern.
example patern with all posible shifts
I found out, that Polyas enumeration theorem can tell you the total number of colorings. I just found examples, where they calculate the unique permutations for roational and mirros symetries.
- Could you please help me to find the answer for the total number of unique patterns?
- Is there a function which can generate all possible unique patterns?
Extra
I found out that the squared Fourier transform can tell whether two (shifted) patterns are the same.
Application
The patterns are used as inputs for a simulation program. The simulation gives the same result for all shifted representation of a pattern. The computation time could be greatly reduced by eliminiating all the redundant patterns.
Thank you very much for helping me out :)
The symmetry group can be generated from two generators: a horizontal rotation $h$ of order $M$ and a vertical rotation $v$ of order $N$, where $h$ and $v$ commute. Therefore it is isomorphic to the direct product of two cyclic groups: $C_M \times C_N$, and PET says that the number of distinct patterns is
$$\frac {1}{MN}\sum_{a=0}^{M-1} \sum_{b=0}^{N-1} C^{c(h^a v^b)}$$
where $c(h^a v^b)$ is the number of cycles in the permutation $h^a v^b$ of the grid. By considering the well-known cycle index of the cyclic group we get (see e.g. Counting Toroidal Binary Arrays, S. N. Ethier, Journal of Integer Sequences vol. 16 (2013))
$$\frac {1}{MN}\sum_{c\mid M} \sum_{d \mid N} \varphi(c) \varphi(d) C^{MN/\ \textrm{lcm}(c,d)}$$