Coloring the Vertices of a Square

Let's begin by coloring the vertices of a square using white and gold. If we fix the position of the square in the plane, there are \(2^4=16\) different colorings. These colorings are shown in .

However, if we think of the square as a metal frame with a white bead or a gold bead at each corner and allow the frame to be rotated and flipped over, we realize that many of these colorings are equivalent. For instance, if we flip coloring \(C_7\) over about the vertical line dividing the square in half, we obtain coloring \(C_9\). If we rotate coloring \(C_2\) clockwise by \(90^\circ\), we obtain coloring \(C_3\). In many cases, we want to consider such equivalent colorings as a single coloring. (Recall our motivating example of necklaces made of colored beads. It makes little sense to differentiate between two necklaces if one can be rotated and flipped to become the other.)

To systematically determine how many of the colorings shown in are not equivalent, we must think about the transformations we can apply to the square and what each does to the colorings. Before examining the transformations' effects on the colorings, let's take a moment to see how they rearrange the vertices. To do this, we consider the upper-left vertex to be \(1\), the upper-right vertex to be \(2\), the lower-right vertex to be \(3\), and the lower-left vertex to be \(4\). We denote the clockwise rotation by \(90^\circ\) by \(r_1\) and see that \(r_1\) sends the vertex in position \(1\) to position \(2\), the vertex in position \(2\) to position \(3\), the vertex in position \(3\) to position \(4\), and the vertex in position \(4\) to position \(1\). For brevity, we will write \(r_1(1) =2\), \(r_1(2)=3\), We can also rotate the square clockwise by \(180^\circ\) and denote that rotation by \(r_2\). In this case, we find that \(r_2(1) = 3\), \(r_2(2)=4\), \(r_2(3)= 1\), and \(r_2(4)=2\). Notice that we can achieve the transformation \(r_2\) by doing \(r_1\) twice in succession. Furthermore, the clockwise rotation by \(270^\circ\), \(r_3\), can be achieved by doing \(r_1\) three times in succession. (Counterclockwise rotations can be avoided by noting that they have the same effect as a clockwise rotation, although by a different angle.)

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.