There is a $n*n$($n$ is an odd number) chess board, which we have to color by white and black.

Question

There is a $n*n$($n$ is an odd number) chess board, which we have to color by white and black. Two colourings are identical if they can be obtained from each other by reflecting or rotating the chessboard. Find the number of colourings.

Well, all the possible colorings are $2^{9}$ There is only one opportunity to make every point white and it's true also for black. I tried to draw $(0,1)$ matrices but after a while the counting seemed to be impossible. I've read articles about Pólya's theorem in the topics and I found also the Burnside lemma. I would appreciate any kind of help to solve this problem.

Answer 1

We can use polya enumeration.

Think of it as a set $X$ consisting of the $2^{n^2}$ colorings of the board, the group that is acting on $X$ is $D_{2\times 4}$ , we want to count the number of orbits in the action.

• The rotation by $0$ degrees fixes all $2^ {n^ 2}$ colorings.
• The rotation by $90$ and $270$ degrees split the squares into $\frac{n^ 2 -1}{4}+1$ orbits and thus there are $2^ {\frac{n^2-1}{4}+1}$ colorings fixed by each of these (in fact they fix the exact same ones, although this is irrelevant)
• The rotation by $180$ degrees splits the squares into $\frac{n^ 2 -1}{2}+1$ orbits and thus there are $2^ {\frac{n^2-1}{2}}+1$ colorings fixed by it.
• all of the reflections split the squares into $\frac{n^ 2-n}{2}+n$ orbits and thus fix $2^{\frac{n^ 2+n}{2}}$ colorings.

We conclude the number of orbits of the action is:

$$\frac{2^{n^2} + 2\times 2^ {\frac{n^2-1}{4}+1} + 2^ {\frac{n^2-1}{2}+1} + 4\times 2^{\frac{n^ 2+n}{2}}}{8}$$