Orbits of a 4x4 checkerboard

485 Views Asked by At

Suppose we have a $4\times4$ checkerboard with 16 squares. Let $S$ be the set of all colorings with 8 black and 8 white colors. Note: colorings are considered the same if they map to each other using rotations and reflections.

Let $G=\{ e, A,B,C,D,90^\circ,180^\circ,270^\circ\}$ be the group of symmetries where $A$ and $B$ are vertical and horizontal reflections, $C$ and $D$ are diagonal reflections, and $90^\circ,180^\circ,270^\circ$ are the rotations. Let $S^g$ be the set of elements fixed by an element $g\in S$. Then: $$|S^e|=\binom{16}{8}$$ $A$ and $B$ reflect halves, so each side must have 4 black squares (and 4 white): $$|S^A|=|S^B|=\binom{8}{4}$$ Since $90^\circ$ and $270^\circ$ project to all 4 quadrants, we get $$|S^{90^\circ}|=|S^{270^\circ}|=\binom{4}{2}$$ Similarly, $180^\circ$ exchanges halves: $$|S^{180^\circ}|=\binom{8}{4}$$ For $C$ and $D$, there are either 2 or 4 black squares along the diagonal. Otherwise, we would reach a contradiction as an odd number of black squares must be split evenly into two halves. Case 1: 2 black squares on diagonal. In this case, we have 6 squares left which are split into 3 per half (out of 6 available squares), so we have $\binom{6}{3}$. But there are $\binom{4}{2}$ different ways of arranging the black squares on the diagonal. Thus, for Case 1 we have $\binom{6}{3}\binom{4}{2}$. For Case 2 (4 black squares on diagonal), each side has 6 total squares and 2 black squares, which is $\binom{6}{2}$. Combining the cases, we get: $$|S^C|=|S^D|=\binom{6}{3}\binom{4}{2}+\binom{6}{2}$$ By Burnside's Lemma, the number of orbits $|S/G|$ is given by $$|S/G|=\frac{1}{|G|}\sum_{g\in G}|S^g|=\frac{1}{8}\left[\binom{16}{8}+3\binom{8}{4}+2\binom{4}{2}+ 2\left[\binom{6}{3}\binom{4}{2}+\binom{6}{2}\right] \right]$$ But this cannot be right, because I put it in Wolfram Alpha and got 1670.25. Obviously, we expect an integer. Where did I go wrong?

1

There are 1 best solutions below

1
On BEST ANSWER

For C and D, there are either 2 or 4 black squares along the diagonal.

Or 0. I got 1674 orbits with this correction.