Coloring vertices of a square

Question

Using four colors, red, white, blue and green, in how many ways can the vertices of a square be colored? Assume that reflections and rotations are allowed, meaning that if you examine a square from front or back it represents the same coloring, and if you turn it, it represents the same coloring. Also assume that no vertex is left uncolored.

Answer 1

Well if I understand your question correctly, we're dealing with a square, you say, so we have four vertices, lets call them 1, 2, 3 and 4.

Then we have four colours, lets call them r, w, b and g for red, white, blue and green.

So given that you say turning a square, I assume you mean rotating it by 90 degrees, it's the same, we don't need to bother adding on these ways.

So working around the square, for vertix 1, we have four choices of colour, r, w, b and g.

Then for vertix 2 we also have four choices of colour, r, w, b and g.

Similarly for vertix 3 we also have four choices of colour, r, w, b and g.

And finally similarly for vertix 4 we also have four choices of colour, r, w, b and g.

So in total we have

4 choices $\times$ 4 choices $\times$ 4 choices $\times$ 4 choices

or $$4 \times 4 \times 4 \times 4 = 4^4 = 256$$

Does this make sense to you?

You have not mentioned if we are aloud to use the same colour more than, I have here assumed that we can.

If we cannot, then it becomes, for vertix 1, we have four choices of colour, a, b, c and d.

Then for vertix 2 we also have three choices of remaining colours.

For vertix 3 we also have two choices of remaining colours.

And finally for vertix 4 we haveonly one choice of the single remaining colour.

So in total we would have

4 choices $\times$ 3 choices $\times$ 2 choices $\times$ 1 choices

or $$4 \times 3 \times 2 \times 1 = 4! = 24$$

I hope this helps.

Answer 2

If we are looking to find all the 4-colourings of a squares vertices such that colours obtained from rigid motions are considered equivalent, then algebraically this is the same as asking "How many orbits does $D_8$ have on the set of $4^4$ vertex colourings?"

Burnsides lemma, informally speaking but good enough here, says that the number of orbits is equal to the average number of "fixed colourings" (that is, those which remain identical after some element of $D_8$ acts on it).

Permutations, of course, may always be written as a product of disjoint cycles, and this is the key to finding the number of fixed colourings for a given "type" of element: If we take $(12)(34)$, then if vertices $1,2$ are coloured the same (and similarly for vertices $3,4$) then the colouring remains fixed under this permutation, as we would simply be permuting the names of vertices of the same colour. There are 4 colours available, so there are $4^2$ possible colourings here; a colour for each disjoint cycle of vertices.

In short, the number of fixed colourings for a permutation (suppose it's a product of $n$ disjoint cycles) is then (number of available colours)$^n$.

So we can list the element "types" (how it is made up of disjoint cycles), and how many such elements there are, to find the average number of fixed colourings:

\begin{tabular}{|c|c|c|c|} \hline Element Type & Example & No. of elements & No. fixed colourings \\ \hline id & $(1)(2)(3)(4)$ & 1 & $4^4$ \\ \hline Rotate $\pm\frac{\pi}{2}$ & $(1234)$ & 2 & $4$ \\ \hline Rotate $\frac{\pi}{2}$ & $(13)(24)$ & 1 & $4^2$ \\ \hline Reflect Horiz/Vert & $(14)(23)$ & 2 & $4^2$ \\ \hline Reflect Diag & $(1)(24)(3)$ & 2 & $4^3$ \\ \hline \end{tabular}

Now then the total number of elements is of course $8$ and the total number of fixed colourings is the number of fixed colourings for a type, times how many elements of that type we have, summed. This gives $440$.

Hence the average number of fixed colourings is $\dfrac{440}{8} = 55$. Which, by Burnsides lemma is the number of orbits, which by definition of an orbit is the number of distinct vertex colourings of a square under the action of $D_8$.

EDIT: I have no idea how to fix the table.. my first try at one on this site, and apparently the usual LaTeX isn't good enough..