0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you talking about a 3x3 matrix for your example? I think with a 3x3 it is feasible to consider all of the group actions, and their corresponding orbits. $\endgroup$ – Prototank May 4 '18 at 17:57
3
$\begingroup$

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}$$

$\endgroup$
  • 1
    $\begingroup$ There had been a mistake, I hadnt read the "reflection" part, the new edit accounts for this. $\endgroup$ – Jorge Fernández Hidalgo May 4 '18 at 18:08
  • $\begingroup$ and is it very different if n is an even number? $\endgroup$ – Zauberkerl May 4 '18 at 18:17
  • 1
    $\begingroup$ no, there are just some minor modifications. $\endgroup$ – Jorge Fernández Hidalgo May 4 '18 at 18:18
  • 1
    $\begingroup$ the number of orbits for the $4$ summands are $n^2,n^2/4,n^2/2, n(n+1)/2$ $\endgroup$ – Jorge Fernández Hidalgo May 4 '18 at 18:21
  • 1
    $\begingroup$ indeed.${}{}{}{}{}$ $\endgroup$ – Jorge Fernández Hidalgo May 4 '18 at 18:25

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.