Counting Shaded Squares In a $4 \times 4$ square, how many different patterns can be made by shading exactly two of the sixteen squares?  Patterns that can be matched by flips and/or turns are not considered different. 
How many different patterns can be made for a $5\times5$ square?
Would the answers be $15$ and $36$ respectively?
How about an $n \times n$ square? 
Would there be two answers for the $n\times n$ square: an answer for each odd and even dimensions? 
Edit:
MJD I don't see how to apply the Cauchy-Frobenius-Burnside-Redfield-Pólya lemma. Can you show me how to apply it for a $3 \times 3$ case? I can verify the answer for that case. 
 A: 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:


*

*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.

*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.

*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.

*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.

*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.
