1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If we are not worried about symmetries of the grid, it should be $3^{25}$. $\endgroup$ – André Nicolas Apr 27 '16 at 21:07
  • 1
    $\begingroup$ @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. $\endgroup$ – André Nicolas Apr 27 '16 at 21:12
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.