# Does this generalisation of Latin squares have a name?

I am interested in looking at $n\times n$ tableaux (or matrices) in which (WLOG) each integer in $\{ 1, 2, \ldots, n \}$ occurs exactly $n$ times. This is a generalisation of a Latin (or even semi-Latin) square, which obviously has this property. It is a proper generalisation, as there are tableaux with this property that are not semi-Latin, such as $$\left[\begin{matrix} 1&2&2\\3&1&3\\3&1&2\end{matrix}\right].$$ I have counted the number of such tableaux, up to a suitable (for my applications) notion of isomorphism for $n = 2,3,4$, and there are lots of them. There are $5$ with $n = 2$; $305$ with $n = 3$; and $2630904$, with $n = 4$. As these generalise Latin squares, it seems like the sort of thing that people in the combinatorics community might have investigated. Have such tableaux been studied before? Do they have a name? (If these have a name, I might do better with Google.) Many thanks.

EDIT: For the $2\times 2$ case, there are $6 = {4\choose 2}$ squares, since we can choose any two of the four matrix positions in which to place a $1$, and then the other two spots must contain a $2$. These are: $$\left\{ \left[\begin{matrix}1&1\\2&2\end{matrix}\right], \left[\begin{matrix}1&2\\1&2\end{matrix}\right], \left[\begin{matrix}1&2\\2&1\end{matrix}\right], \left[\begin{matrix}2&1\\1&2\end{matrix}\right], \left[\begin{matrix}2&1\\2&1\end{matrix}\right], \left[\begin{matrix}2&2\\1&1\end{matrix}\right]\right\}.$$ Now, of these, only the pair $\left[\begin{matrix}1&2\\2&1\end{matrix}\right]$ and $\left[\begin{matrix}2&1\\1&2\end{matrix}\right]$ are equivalent.

The notion of equivalence or isomorphism used is this. Two such $n\times n$ matrices $(a_{i,j})$ and $(b_{i,j})$ as above, are regarded as essentially the same if there is a permutation $\sigma\in S_{n}$ for which $\sigma( a_{i,j} ) = b_{\sigma i, \sigma j}$, for all $i$ and $j$.

-
What is said notion of isomorphism? – Alex Becker Dec 31 '11 at 2:05
@AlexBecker: Isomorphism is defined as follows. Think of these as $n\times n$ matrices. Then $(a_{i,j})$ and $(b_{i,j})$ are isomorphic if there is a permutation $\sigma\in S_{n}$ for which $\sigma a_{i,j} = b_{\sigma i,\sigma j}$. – James Dec 31 '11 at 4:52

These are called "equi-n-squares."

-

Before your isomorphism, the tableau representation is not important and you can just view it as a list. As such, you can pick $n$ of the $n^2$ positions for $1$, $n$ of the remaining $n^2-n$ for $2$ and so on. It becomes $$\binom {n^2}n \binom{n^2-n}n \binom {n^2-2n}n \ldots \binom nn$$ I didn't find 2630904 in OEIS. Without the isomorphism it is $\frac{(n^2)!}{(n!)^n}$ which is A034841.

-
I didn't find the sequence (counted up to equivalence) in the OEIS either. I didn't think of trying the sequence without eliminating equivalents, though. Nice. – James Dec 31 '11 at 9:13
@James: I'm not clear on the isomorphism range you are talking about. For $n=2$ it seems you could just define that the upper left is $1$, then the other $1$ can go in any location, so there should be $3$, not $5$. For this, you just divide by one more factor of $n!$. That one is oeis.org/A057599 – Ross Millikan Dec 31 '11 at 16:06
I've added some further explanation to the question body. (It seemed too long for a comment.) Thanks. – James Jan 1 '12 at 2:34

Courtiel and Vaughan, Gerechte designs with rectangular regions, JCD (2012) calls them a gerechte framework.

A gerechte framework is a partition of an $n \times n$ array into $n$ regions of $n$ cells each.

This definition comes from a gerechte design, which is a Latin square together with the entries partitioned into sets of size $n$ such that each part contains each symbol exactly once (like sudoku).

In 1956, W. U. Behrens [4] introduced a specialisation of Latin squares which he called “gerechte”. --- Bailey, Cameron, Connelly. AMM (2008). (pdf)

W. U. Behrens, Feldversuchsanordnungen mit verbessertem Ausgleich der Bodenunterschiede, Zeitschrift für Landwirtschaftliches Versuchs- und Untersuchungswesen 2 (1956), 176-193.

(Unfortunately, I don't have access to this paper, so my trail ends here.)

-
Many thanks! I don't think I can get that (Behrens) paper either but, even if I could, I can't read German. (I guess it is German.) But I'll look at the other papers you've kindly provided. – James Jul 13 '14 at 6:12