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?


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

Or 0. I got 1674 orbits with this correction.

  • $\begingroup$ Oh I overlooked that. Thanks. $\endgroup$ – Patrick Shambayati Mar 5 '15 at 22:26

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.