Number of ways to color a grid

Question

Consider a $2000 \times 2000$ matrix which is to be filled with $15$ colors. Find the number of ways to color the matrix. Two colorings are same if rotating one of them along the axis perpendicular to the plane (in multiples of 90 degrees) gives the other. Find the number of ways to color it.

Can anyone help me? I have no idea how to solve this. I could only solve the problem when there are two and three colors ( for only small matrices such as 3*3 and 4*4 ,i did it by hand), but more than that I couldn't.

Answer 1

Working with a $2N\times 2N$ matrix, we have by inspection the cycle index

$$Z(M_{2N}) = \frac{1}{4} (a_1^{4N^2} + 2 a_4^{N^2} + a_2^{2N^2}).$$

Therefore we get for colorings using at most $C$ colors the closed form by Burnside

$$\frac{1}{4} (C^{4N^2} + 2 C^{N^2} + C^{2N^2}).$$

This gives for two colors the sequence

$$6, 16456, 17179934976, 4611686019501162496, \\ 316912650057057631849169289216,\ldots $$

which points to OEIS A047937, where these data are confirmed.

For colorings using exactly $C$ colors we find

$$\frac{C!}{4} \left({4N^2\brace C} + 2 {N^2\brace C} + {2N^2\brace C}\right).$$

We get for a four by four board starting with exactly one color the sequence

$$1, 16454, 10713996, 1030803624, 32885748000, 492286828320, \\ 4135172116320, 21588981664320,\ldots$$

This sequence is finite as we can place at most sixteen colors.

In the question being asked we have $N=1000$ and $C=15.$

Answer 2

The following does not use Burnside's Lemma, or similar.

We have a quadratic table $A$ with $(2n)\times(2n)$ cells, and there are $c$ colors. The table $A$ has four cyclically arranged quarters. There are $c^{n^2}=:N$ different colorings of the cells in a quarter. Two quarters are equally colored if a $k\times90^\circ$ rotation of $A$ around its center carries one into the other.

It follows that we now have $N$ colors (actually "pictures") to color each of the four quarters. This can be done in $N^4$ ways. But we have to take care of the $k\cdot90^\circ$ rotations. There are $N$ colorings of type $(x,x,x,x)$. These colorings produce just one case under the four rotations. Then there are $N(N-1)$ colorings of type $(x,y,x,y)$ with $x\ne y$. Each of these produces two cases under rotation. All other colorings $(x_1,x_2,x_3,x_4)$ produce four different cases under rotation. It follows that the total number $T$ of different cases is given by $$T={1\over4}\bigl(N^4-N-N(N-1)\bigr)+N+{1\over2}N(N-1)={1\over4}(N^4+N^2+2N)\ .$$ This coincides with the second formula of Marko Riedel.