Return to Answer

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.

To use the Cauchy–Frobenius–Burnside–Redfield–Pólya lemma, we first divide the 8 symmetries of the square into five conjugacy classes, and count 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$ of the possible 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 color two one-square orbits, for a total of $n^2-n$ colorings fixed by these flips.
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 fixed.

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{2\cdot0}_{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 check as follows: There are three kinds of squares in a $4×4$ array: corners, edges, and centers.

• There are 2 ways to share two center squares.
• There are 2 ways to shade two corner squares.
• After shading one of the edge squares, there are 6 ways to shade another edge square. (The seventh, with the two shaded squares separated by a knight's move, is equivalent under $90^\circ$ rotation to one of the others.)
• After shading a center square, there are 3 ways to shade a corner square.
• After shading a center square, there are 4 ways to shade an edge square.
• After shading a corner square, there are 4 ways to shade an edge square.

That's 21 shadings total, which checks.

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.

To use the Cauchy–Frobenius–Burnside–Redfield–Pólya lemma, we first divide the 8 symmetries of the square into five conjugacy classes, and count 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$ of the possible 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 color two one-square orbits, for a total of $n^2-n$ colorings fixed by these flips.
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 fixed.

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{2\cdot0}_{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 check as follows: There are three kinds of squares in a $4×4$ array: corners, edges, and centers.

• There are 2 ways to shade two center squares.
• There are 2 ways to shade two corner squares.
• After shading one of the edge squares, there are 6 ways to shade another edge square. (The seventh, with the two shaded squares separated by a knight's move, is equivalent under $90^\circ$ rotation to one of the others.)
• After shading a center square, there are 3 ways to shade a corner square.
• After shading a center square, there are 4 ways to shade an edge square.
• After shading a corner square, there are 4 ways to shade an edge square.

That's 21 shadings total, which checks.

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.

To use the Cauchy–Frobenius–Burnside–Redfield–Pólya lemma, we first divide the 8 symmetries of the square into five conjugacy classes, and count 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$ of the possible 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 color two one-square orbits, for a total of $n^2-n$ colorings fixed by these flips.
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 fixed.

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{2\cdot0}_{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 check as follows: There are three kinds of squares in a $4×4$ array: corners, edges, and centers.

• There are 2 ways to share two center squares
• There are 2 ways to shade two corner squares
• After shading one of the edge squares, there are 6 ways to shade another edge square. (The seventh, with the two shaded squares separated by a knight's move, is equivalent under $90^\circ$ rotation to one of the others.)
• After shading a center square, there are 3 ways to shade a corner square.
• After shading a center square, there are 4 ways to shade an edge square.
• After shading a corner square, there are 4 ways to shade an edge square.

That's 21 shadings total, which checks.

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.

To use the Cauchy–Frobenius–Burnside–Redfield–Pólya lemma, we first divide the 8 symmetries of the square into five conjugacy classes, and count 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$ of the possible 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 color two one-square orbits, for a total of $n^2-n$ colorings fixed by these flips.
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 fixed.

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{2\cdot0}_{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 check as follows: There are three kinds of squares in a $4×4$ array: corners, edges, and centers.

• There are 2 ways to share two center squares.
• There are 2 ways to shade two corner squares.
• After shading one of the edge squares, there are 6 ways to shade another edge square. (The seventh, with the two shaded squares separated by a knight's move, is equivalent under $90^\circ$ rotation to one of the others.)
• After shading a center square, there are 3 ways to shade a corner square.
• After shading a center square, there are 4 ways to shade an edge square.
• After shading a corner square, there are 4 ways to shade an edge square.

That's 21 shadings total, which checks.

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{2\cdot0}_{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.

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.

To use the Cauchy–Frobenius–Burnside–Redfield–Pólya lemma, we first divide the 8 symmetries of the square into five conjugacy classes, and count 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$ of the possible 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 color two one-square orbits, for a total of $n^2-n$ colorings fixed by these flips.
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 fixed.

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{2\cdot0}_{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 check as follows: There are three kinds of squares in a $4×4$ array: corners, edges, and centers.

• There are 2 ways to share two center squares
• There are 2 ways to shade two corner squares
• After shading one of the edge squares, there are 6 ways to shade another edge square. (The seventh, with the two shaded squares separated by a knight's move, is equivalent under $90^\circ$ rotation to one of the others.)
• After shading a center square, there are 3 ways to shade a corner square.
• After shading a center square, there are 4 ways to shade an edge square.
• After shading a corner square, there are 4 ways to shade an edge square.

That's 21 shadings total, which checks.