In how many ways can you colorize the vertices of an $(n\times n)$-square forming an $(n+1)$-grid with $4$ colors so that every unit-square vertices are all of a different color ?
Precisions:
$(n\times n)$-square: square whose edge length is $n$.
$(n+1)$-grid: square grid containing $(n+1)$ vertices per side, and composed of $n^2$ unit-squares of dimension $(1\times 1)$.
Here are some examples for $n=1,2,3$
My attempt:
I have posted a similar question here I tried to do the same way (Because the answer is like that too ($24\times (2^{n}-1)$)) but it didn't answer.
Any hints?
Best Answer
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.
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.