1

I am working on a problem related to counting the number of different colorings on the vertices of a square assuming that the colorings resulting from rotations and reflections are considered the same.

The problem is as follows:

How many ways are there to 4-color the corners of a square with rotations and reflections allowed if adjacent corners must have different colors.

If we label the corners as $\{1,2,3,4\}$, then under rotation and reflection, we have the following cycles: $(1)(2)(3)(4)$, $(1234)$, $(13)(24)$, $(1432)$, $(14)(23)$, $(12)(43)$, $(1)(24)(3)$, $(13)(2)(4)$.

I tried to use the Cauchy-Frobenius-Burnside (CFB) Theorem to count the different possibilities but could not get anything. Any help will be appreciated.

Morteza Soltani
  • 193

1 Answers1

3

Let's do the Burnside. There are $8$ symmetries (I like to think of them geometrically rather than in abstract cycle notation). The number of squares which are invariant for each of these symmetries are:

  • The trivial symmetry: This is just all possible colourings, without taking symmetries into account. Corner 1 can have $4$ different colours, and corner 2 can then have $3$ different colours. If the corner diagonally opposite corner 2 has the same colour as corner $2$, then the final corner has $3$ options. Otherwise it has $2$. That's a total of $4\cdot 3(3 + 2\cdot 2)= 84$
  • The two $90^\circ$ rotations: Adjacent corners must have different colours, so no invariants here
  • The $180^\circ$ rotation: Corner 1 can be any of the $4$ colours, corner $2$ can have any of the remaining $3$, and the two remaining corners are then fixed. $12$ invariants
  • The two mirrorings with axis a diagonal: The two corners not on the axis must have the same colour, and can have any of $4$ colours, and the two fixed corners can choose freely and independently from the $3$ remaining colours, giving $4\cdot 3^2 = 36$ invariants
  • The two mirrorings with axis perpendicular to a side: Adjacent corners are sent to one another, so no invariants here

Burnside's lemma then tells us that the number of distinct squares, taking the symmetries into account, is $$ \frac{84 + 0 + 0 + 12 + 36 + 36 + 0 + 0}8 = 21 $$

Arthur
  • 199,419