Skip to main content
1 of 5
MJD
  • 68k
  • 44
  • 311
  • 627

The analysis is different depending on whether $n$ is even or odd. I will do the case of $n$ even, and leave odd $n$ to you.

Using the Cauchy–Frobenius–Burnside–Redfield–Pólya lemma, we first divide the 8 symmetries of the square into five conjugacy classes, and acount the number of colorings that are left fixed by each symmetry:

  1. A horizontal or vertical flip divides the squares into $\frac12n^2$ orbits of 2 squares each. For a coloring to be fixed by this reflection, both shaded squares must be in the same orbit, so these symmetries each fix exactly $\frac12n^2$ colorings.
  2. The two diagonal flips divide the squares into $n$ single-square orbits (along the diagonals) plus $\frac12(n^2-n)$ two-square orbits (elsewhere), Either one of the two-square or two of the one-square orbits must be shaded. There are $\frac12(n^2-n)$ two-square orbits, plus $\frac12{n^2-n}$ ways to share two one-square orbits, for a total of $n^2-n$ colorings.
  3. A $90^\circ$ clockwise or counterclockwise rotation divides the squares into $\frac14n^2$ orbits of 4 squares each. There is no way to shade two squares that will be fixed by a $90^\circ$ rotation.
  4. A $180^\circ$ rotation divides the squares into $\frac12n^2$ orbits of 2 squares each, so there are $\frac12n^2$ colorings that are fixed by this symmetry.
  5. The identity symmetry divides the squares trivially into $n^2$ orbits of 1 square each. Any two squares can be shaded, so $\frac12n^2(n^2-1)$ colorings are dixed.

By the CFBRP lemma, the number of distinct colorings of the $n\times n$ array, (where $n$ is even) is the average number of colorings left fixed by each symmetry:

$$\frac18\left( \underbrace{2\left(\frac12n^2\right)}_{\text{horiz / vert flip}} + \underbrace{2(n^2-n)}_{\text{diag flip}}+ \underbrace{0}_{90^\circ\text{ rot.}}+ \underbrace{\frac12n^2}_{180^\circ\text{ rot.}} + \underbrace{\frac12n^2(n^2-1)}_{\text{identity}} \right).$$

This simplifies to: $$\frac18\left(\frac12n^4+3n^2-2n\right).$$ Taking $n=2$, for example, we get 2, which is correct: you can color two adjacent squares, or two squares on a diagonal. Taking $n=4$ we get 21, which I will hand-check after I put the kids to bed.

MJD
  • 68k
  • 44
  • 311
  • 627