In how many ways can you colorize the vertices of a grid with 4 colors so that every unit-square vertices are all of a different color?

Solution 1:

Consider a rectangular grid containing $m$ squares in each column and $n$ squares in each row. Label the rows of squares by the indices $1$, $2$, ..., $m$ and the rows of vertices by the indices $0$, $1$, ..., $m$ and do similarly for columns. Suppose that the vertices of the grid have been colored in such a way that every one of the $mn$ squares contains a vertex of each color.

Now suppose that a new row of squares is added to the grid. Can the previous coloring be extended to the last row of vertices (row $m+1$)? If so, in how many ways? The answer to the first question is that it can. This is so because we can color row $m+1$ the same way we colored row $m-1$. To answer the second question, notice that, once the color of any vertex in the row is decided, the colors of all the remaining vertices in the row are determined, assuming a coloring is possible at all. (Successively color neighbors of previously colored vertices until the whole row is colored. Each vertex that gets colored is the fourth member of a square in which three vertices have already been colored. Either the fourth color will be uniquely colored or two of the three colors already used will be the same, making the coloring untenable.) Since the first vertex can be colored in two ways, we conclude that row $m+1$ has at least one coloring and at most two colorings.

To determine whether the number of colorings is one or two, observe that if the coloring of row $m$ uses three or four colors, than at some point in the row we will have $$ m:\ \ldots abc\ldots, $$ where $a$, $b$, and $c$ are different colors. The colors in the corresponding positions in row $m+1$ are then forced, $$ \begin{aligned} m:&\ \ldots abc\ldots\\ m+1:&\ \ldots cda\ldots, \end{aligned} $$ where $d\notin\{a,b,c\}$. In fact, the colors in the corresponding positions in row $m-1$ are forced in the same way, and rows $m-1$ and $m+1$ are therefore colored identically. So in this case there is one coloring of row $m+1$. Also, the number of colors used in column $n$ will not be changed by the addition of row $m+1$.

If row $m$ uses only two colors, then two colorings are possible for row $m+1$, $$ \begin{aligned} m:&\ abababa\ldots & m:&\ abababa\ldots\\ m+1:&\ cdcdcdc\ldots & m+1:&\ dcdcdcd\ldots. \end{aligned} $$ The number of colors used in column $n$ may be changed by the addition of row $m+1$.

Observe that if a row uses only two colors, then all preceding and subsequent rows only use two colors; if a row uses three or more colors, then all preceding and subsequent rows use three or more colors. Clearly similar considerations apply to columns.

We are now in a position to write a system of recurrences for the number of colorings of an $m\times n$ grid. Define $$ \begin{aligned} Q_{m,n}&=\text{num. colorings with two colors in row $m$, two colors in column $n$,}\\ R_{m,n}&=\text{num. colorings with two colors in row $m$, three colors in column $n$,}\\ S_{m,n}&=\text{num. colorings with three colors in row $m$, two colors in column $n$,}\\ T_{m,n}&=\text{num. colorings with three colors in row $m$, three colors in column $n$.} \end{aligned} $$ Then $$ \begin{aligned} \begin{bmatrix}Q_{1,1} & R_{1,1}\\ S_{1,1} & T_{1,1}\end{bmatrix}&=24\cdot\begin{bmatrix}1 & 0\\ 0 & 0\end{bmatrix}\\ \begin{bmatrix}Q_{m,n} & R_{m,n}\\ S_{m,n} & T_{m,n}\end{bmatrix}&=\begin{bmatrix}Q_{m-1,n} & Q_{m-1,n}+2R_{m-1,n}\\ S_{m-1,n} & T_{m-1,n}\end{bmatrix}=\begin{bmatrix}Q_{m,n-1} & R_{m,n-1}\\ Q_{m,n-1}+2S_{m,n-1} & T_{m,n-1}\end{bmatrix} \end{aligned} $$ From this it is not hard to obtain the result you need.

For a conceptual explanation, observe that $T_{m,n}=0$ for all $m$, $n$. So either all rows use only two colors, or all columns use only two colors, or both. If all rows use only two colors then, since there are $4!=24$ colorings for the first square in row $1$, and since the coloring of the first two rows of vertices is determined by the choice of coloring for this square, there are $24\cdot2^{m+1-2}=24\cdot2^{m-1}$ colorings of the grid in this case. Similarly, the number of colorings in the case that all columns use only two colors is $24\cdot2^{n-1}$. Using inclusion-exclusion, the total number of colorings of the grid is $24\cdot\left(2^{m-1}+2^{n-1}-1\right)$ colorings.

Added summary: Let's formalize and flesh out a few details of the conceptual explanation above.

Proposition: If an $m\times n$ grid, $m,n\ge1$, has been four colored so that each of the four colors is used in every square then at least one of the following holds.

1. Only two colors are used in each row of vertices.
2. Only two colors are used in each column of vertices.

Proof: Observe that if a row or column uses only two colors, then the colors in that row or column alternate, $ababab\ldots$. Now perform induction on the number of squares in the grid. The base case is the case of one square, for which the statement clearly holds. For the induction step, at least one of $m$, $n$ is greater than $1$. Let's say $m$ is. Then, by the induction hypothesis, the statement holds for the four coloring of the $(m-1)\times n$ grid obtained by deleting the last row of vertices. Suppose that the rows of this smaller grid each use only two colors. If the colors in the last row of this smaller grid are $ababab\ldots$, then the colors in the deleted row can only be $cdcdcd\ldots$ or $dcdcdc\ldots$, where $c$ and $d$ are the two colors different from $a$ and $b$. If the rows of the smaller grid each use three or more colors, then the columns each use only two colors. Furthermore, the deleted row (row $m$) is colored the same as row $m-1$, and hence introduces no new color into any column. $\square$

Now if the rows each use only two colors, then let row $0$ be colored $ababab\ldots$ and let row $1$ be colored $cdcdcd\ldots$. There are $4!$ choices for the colors $a$, $b$, $c$, $d$. Then each of rows $2$, $4$, $6$, etc. must be colored either $ababab\ldots$ or $bababa\ldots$, and each of rows $3$, $5$, $7$, etc. must be colored either $cdcdcd\ldots$ or $dcdcdc\ldots$. Hence there are $24\cdot2^{m-1}$ colorings in this case. Similarly, in the case that the columns each use only two colors, there are $24\cdot2^{n-1}$ colorings. We over-count if we simply add the number of colorings in each of the two cases since there are $4!$ colorings in which both rows and columns each use only two colors. Hence the total number of colorings is $24\cdot(2^{m-1}+2^{n-1}-1)$. Specializing to the case where $m=n$, we get $24\cdot(2^m-1)$ colorings.

Solution 2:

I thought about this for a while and came to a conclusion:

No. of Ways to Colour = $4!*(2^n-1)$!

In the case of an nxn grid, you can consider it to be an $(n-1)$ by $(n-1)$ grid with $2n-1$ vertices wrapped around it. Next, imagine that the $n-1$ grid is already coloured. Look at this photo:

Then, to colour the "layer" around it, we have 2 ways to colorize the vertices on the unit-box in the bottom righthand corner. Then, moving upwards, all the vertices up to the top-righthand corner are determined, since two of the colours have been defined by the $(n-1)$ grid and the bottom righthand corner of each box is chosen by the one below (ending at one of the 2 choices for the bottom righthand one).

At the top righthand corner, we again meet 2 choices, since you have the top righthand vertex of the $(n-1)$ grid and another is coloured from the ones determined around the edge, and then the rest of the colours are determined.

Thus, for an n-sized grid there are $4*(n-1)$ ways of colorizing the vertices satisfying the conditions above. However, if we look more carefully, we can find cases where only one of these 2 choices are given to us and that in fact, we only ever get one of these 2 choices. Consider the case where one of our 2 colours to "choose" from is also the colour of the vertex 2 up, 1 left from the bottom righthand corner. If this was true, we would only have one choice in how we arrange the colours, and that would be the same as the penultimate column of the $(n-1)$ box.

If this was true, another consequence would be that you could still choose one of 2 configurations in the top righthand corner, since we know the reflected columns fact. However, if in the first case we had 2 choices then by the time we had got to the top righthand corner, we would not have 2 choices there, since the columns would not be reflected.

Thus, we must re-state our formula as $2*(n-1)$.

Now, for n = 1, the number of ways of colouring it such that the colours are different with 4 colours is simply $4! = 4*3*2*1 = 24$.

Thus, we derive the number of ways to colour an n by n grid using 4 colours such that every unit-square vertices are a different colour with 4 colours is $4!*(2^n-1)$.