How many ways is there to color an $n\times n$ square grid with $n$ colors such that each column and each row contains exactly one $1\times 1$ square of each color?
And how many ways if the same is required of the two diagonals?
combinatoricslatin-square
How many ways is there to color an $n\times n$ square grid with $n$ colors such that each column and each row contains exactly one $1\times 1$ square of each color?
And how many ways if the same is required of the two diagonals?
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.
Let's consider separately cases where there are $4,2$ and $3$ different colours in the first column.
Case 1:
$4$ different colors. This has only one pattern since the outermost colors must switch places with the center two colors and there is only one way this can happen. Colors can be chosen in $4!=24$ different ways. $$\begin{bmatrix}a&c&a&c&a\\b&d&b&d&b\\c&a&c&a&c\\d&b&d&b&d\end{bmatrix}$$
Case 2:
$2$ different colors. First column can be constructed in $4\cdot3=12$ ways. There can only be $2$ colors per column, but for every column from $2$ to $5$ there are two possible arrangements. In total there are $12\cdot2^4=192$ solutions.
$$\begin{bmatrix}a&c&a&c&a\\b&d&b&d&b\\a&c&a&c&a\\b&d&b&d&b\end{bmatrix}$$
Case 3:
3 different colors.
I) The first column can not be of the form $$\begin{bmatrix}a\\b\\c\\a \end{bmatrix}$$ (this would imply the two center colors would both be $d$)
II) If the same colors are arranged as follows there is only one pattern (since third row is fixed):
$$\begin{bmatrix}a&d&a&d&a\\b&c&b&c&b\\a&d&a&d&a\\c&b&c&b&c\end{bmatrix}$$
The colors can be chosen in $4\cdot3\cdot2=24$ ways.
III) The last possibility is case II) flipped. $24$ more combinations.
So in total there are $$24+192+2\cdot 24=264$$ ways color the squares such that the conditions are fulfilled.
Best Answer
The exact number of latin squares of order n is known only up to n = 11, and these counts are reflected in the OEIS and Wikipedia entries already linked in the Comments.
For counting "diagonal" latin squares I could not find any ready online reference, so I wrote a quick Prolog program that provides solutions for the smaller orders.
Note that for the sake of counting we may assume a particular first row of the latin square, so that if the first row is $(1,2,...,n)$ it is in partially reduced form (reduced form having also the first column in standard order).
For n = 1 there is the one (trivial) case.
For n = 2,3 one quickly finds there are no diagonal latin squares.
For n = 4 there are two cases in partially reduced form. Therefore the total count is 2*4! = 48.
For n = 5 there are eight cases in partially reduced form, for a total count of 8*5! = 960.
My code is not optimized for speed but is clear, so the next step is to refactor and impose constraints in a more efficient manner to make some higher orders feasible.
Added:
For n = 6 there are 128 cases in partially reduced form, for a total count of 128*6! = 92160. This result was confirmed by a computation using a different normalization, see discussion below.
For n = 7 my preliminary result is a total count of 171200*7! = 862,848,000 solutions.
Using the partially reduced form (first row in standard order) the n = 6 case was enumerated in 6.3 seconds. Analyzing the time consumed in building stages of the search space suggested that normalizing the main diagonal (in standard order) would be better. I posted a Question here, Counting some special derangements, motivated by how this constrains the choice of anti-diagonals. Another feature of this approach is cutting the enumeration in half via the action of matrix transpose.
These efficiencies reduced the computation time for n = 6 to 1.5 seconds. Despite their use in the n = 7 case, the increased size of the search space led to a running time of 1776 seconds, nearly half an hour.
Such a three-order of magnitude increase in running time suggests that the n = 8 case will not be easily solved on a single CPU, even if the code were compiled instead of interpreted. [Update: For the n = 8 case there are 7450228224*8! = 300,393,201,991,680 diagonal latin squares. This was computed on a single CPU through a combination of speeding up the code that searches on a single main diagonal/anti-diagonal assignment and reducing the number of such assignments by equivalences. The code now runs such a single assignment in 1-2 hours. Given normalization of the main diagonal to the identity sequence $1,2,..,8$, there are 4,752 possibilities (µ-derangements) for the anti-diagonal. A first reduction to 630 equivalences classes is made by using orbits under a dihedral group action. A further reduction to 114 enlarged equivalence classes results from taking "orbits of orbits" under a group isomorphic to $(\mathbb{Z}/2\mathbb{Z})^4$ acting by conjugation. Finally it appears we actually need only count 18 distinct cases due to equivalences of a more contingent nature than those group symmetries. Similar results should apply to solving n = 9, though searching each given µ-derangement will take more time.]
While seeking citations for counts of diagonal latin squares I came across this interesting 2009 paper by Zhang and Ma, Counting solutions for the N-queens and Latin-square problems by Monte Carlo simulations, which is freely available through NIH's Pub Med Central. Perhaps their technique could be adapted for estimating counts of diagonal latin squares of "large" orders. More recently (2017) a report Using Volunteer Computing to Study Some Features of Diagonal Latin Squares describes tactics to count them up to order $n=8$.