Problem 1993

Mark the squares of the table as shown below.
In the sequel, the squares that lie symmetric with respect to square $x$ are called symmetric; a square that is marked with odd number is called odd square; a square that is marked with even number is called even square.
Let $s$ denote the number to be found.
We have the following remarks:

* Remark 1: When rotating the table around its center the square marked by $x$ does not move. Hence, denoting by $s_0$ the number of pairwise non-similar ways of painting 8 squares on the border of the table, then $s = n s_0$.

* Remark 2: There are 4 rotations that move the table to itself: the rotation with angle $\alpha$, the rotation with angle $2\alpha$, the rotation with angle $3\alpha$ and the rotation with angle $4\alpha$; where $\alpha = \frac{\pi}{2}$. Under each such rotation, the squares move as follows:
- the rotation with angle $\alpha$: $1 \to 3 \to 5 \to 7 \to 1$ and $2 \to 4 \to 6 \to 8 \to 2$.
- the rotation with angle $2\alpha$: $1 \to 5 \to 1$, $2 \to 6 \to 2$, $3 \to 7 \to 3$ and $4 \to 8 \to 4$.
- the rotation with angle $3\alpha$: $1 \to 7 \to 5 \to 3 \to 1$ and $2 \to 8 \to 6 \to 4 \to 2$.
- the rotation with angle $4\alpha$: each square comes back to its original place.

Let $T$ be the set of ways of painting 8 border squares, such that in each way, each square is painted by one color.
For each $t \in T$, denote $k(t)$ the number of ways of painting that are similar to it.
Consider a way of painting $t \in T$. It follows from Remark 2 that:

$$+\ k(t) = 1 \text{ if and only if the odd squares are painted by the same color.}$$
$$+\ k(t) = 2 \text{ if and only if symmetric squares are painted by the same color, and 4 odd squares or 4 even squares are not painted by the same color.}$$
$$+\ k(t) = 4 \text{ otherwise.}$$

For each $i \in \{1; 2\}$, denote $T_i = \{t \in T \mid k(t) = i\}$. From the arguments above we have:
$$|T_1| = n^2 \quad \text{and} \quad |T_2| = n^4 - n^2.$$
$$\text{Hence:}\ s_0 = \frac{|T| - |T_1| - |T_2|}{4} + \frac{|T_2|}{2} + |T_1| = \frac{|T| + 3|T_1| + |T_2|}{4} = \frac{n^8 + n^4 + 2n^2}{4}.$$
$$\text{Thus:}\ s = n \cdot s_0 = \frac{n^3(n^6 + n^2 + 2)}{4}.$$