Using Group Actions to determine the different colourings of a grid

Question

I am trying to find the number of different colourings of an $n \times n$ grid using $m$ colours by using group actions. The set that I am acting on is the set of $n^2$ ‘tiles’ within the square grid.

I am finding it hard to understand this problem but this is my plan:

I want to define a group action that rotates the grid and then I will calculate the number of different orbits using Burnside’s Lemma.

Once I have the number of different orbits, say $k$. The number of colouring that are the same under rotation is $m^k$.

The problem is I’m struggling to grasp the concept of what the group I choose is doing.

• Does the group I decide determine the orbits? Or does the group not act on the set at all until I define how it acts in some way?

My idea was to let the subgroup of $D_4$, $\langle r \rangle$, be the group as this is the rotation subgroup of the symmetries of a square $D_4$.

• How do I know how this subgroup acts on the set of tiles and in the way I intend it to?

Answer 1

First off, forget the dihedral group and go right for the cyclic group $C_4$ (or $\Bbb Z_4$ if you prefer that). That removes one layer of abstraction.

We pick the group of rotations of the square, because that is the precise group of symmetries that we consider "not to change" the grid in our final answer. We want to consider grids that are rotations of one another to be the same, so the group of rotations is what we're going to look at. If we also considered mirrorings to produce "the same grid", then we would use the dihedral group $D_4$, since that is the group of "rotations and mirrorings".

Let $M$ be the set of the $m^{n^2}$ differently coloured grids (where we do consider rotated grids to be distinct; this is the easy one to count). Then each of the four elements of $C_4$ induces a bijection $M\to M$, intuitively given by rotations by $0^\circ, 90^\circ, 180^\circ$ and $270^\circ$ respectively. The product of elements in $C_4$ corresponds to compositions of rotations. This collection of bijections, and the correspondence between these two operations is called a $C_4$-group action on $M$.

Consider the equivalence relation $\sim$ on $M$ defined by $x\sim y$ iff one of these four bijections takes $x$ to $y$. Then the equivalence classes are called orbits of this action. We are after the number of such orbits.

The vast majority (at least for large $m$ and $n$) of these equivalence classes will have size $4$. So $\frac{m^{n^2}}{4}$ is a decent first approximation to the final answer. However, some will have size $2$ and some will have size $1$, and trying to count the number of orbits of each size directly is a pain.

That's where burnside's lemma comes in. Instead of focusing on the number of equivalence classes of each size, this lemma leverages the orbit-stabilizer theorem to change focus entirely. We now take each of the four bijections, and count the number grids that are mapped to themselves:

• For the $0^\circ$ rotation, that's $m^{n^2}$, as each grid is mapped to itself.
• For the $90^\circ$ rotation, that's going to depend on the parity of $n$. If $n$ is even, there are $m^{n^2/4}$ grids that are mapped to themselves by this rotation, while for odd $n$, the answer is $m^{(n^2 + 3)/4}$.
• For the $180^\circ$ rotation, and even $n$, there are $m^{n^2/2}$ grids that are sent to themselves, while for odd $n$ there are $m^{(n^2+1)/2}$ grids.
• For the $270^\circ$, the answer is the same as for the $90^\circ$

Now just take the average of these four numbers (in each case picking the right one depending on whether $n$ is even or odd), and you get the number of orbits.