# How many distinct patterns exist for a 5x5 grid by filling 3 colors?

Using 3 colors to fill in a $5\times5$ grid (you don't have to use all colors), then how many distinct patterns exist? The "distinct" means we have to consider the symmetry. Any effective approach is appreciated.

• If we are not worried about symmetries of the grid, it should be $3^{25}$. – André Nicolas Apr 27 '16 at 21:07
• @peterwhy: I interpreted "you can use $\dots$" as "you are allowed to use $\dots$" meaning we don't have to use all three. If we cannot use all three, the calculation is a little more complicated, but not much. – André Nicolas Apr 27 '16 at 21:12

Supposing that we want non-isomorphic patterns we need the cycle index $Z(G)$ of the automorphism group $G$ acting on the cells of the grid. We assume full symmetry, which includes rotations and reflections.

We now compute this cycle index. There is the identity which contributes $$a_1^{25}.$$

The $90$ degree and the $270$ degree rotation contribute $$2a_1 a_4^6.$$

The $180$ degree rotation contributes $$a_1 a_2^{12}.$$

The horizontal and vertical reflections contribute $$2a_1^5 a_2^{10}.$$

The reflections in the diagonals contribute $$2a_1^5 a_2^{10}.$$

This yields the cycle index

$$Z(G) = \frac{1}{8} \left(a_1^{25} + 2a_1 a_4^6 + a_1a_2^{12} + 4 a_1^5 a_2^{10}\right).$$

With at most $N$ colors we thus have (by Burnside the colors must be constant on each cycle and there are $N$ colors available)

$$Q_N = \frac{1}{8} (N^{25} + 2N^7 + N^{13}+ 4N^{15}).$$

We get for at most three colors $$105918450471.$$

Remark. If we seek the number of colorings using an exact number of distinct colors like three colors and call the colorings with at most $N$ colors $Q_N$ we have by inclusion-exclusion

$$\sum_{q=1}^N {N\choose q} (-1)^{N-q} Q_q.$$

This produces a finite sequence that starts at $N=1$ and ends at $N=25$ (we cannot place more than $25$ distinct colors on the grid).

We obtain

$$1, 4211742, 105905815242, 140314385087520, 36550287370308180,\ldots, \\ 1938901255416373248000000, 0,\ldots$$

We have $$1938901255416373248000000 = \frac{25!}{8}$$ when $N=25$ as all orbits are the same size in this case.