6
$\begingroup$

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$.

  • 0
    @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}$.2011-12-31

3 Answers 3

3

These are called "equi-n-squares."

1

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.

  • 0
    I've added some further explanation to the question body. (It seemed too long for a comment.) Thanks.2012-01-01
1

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.)

  • 0
    Many thanks! I don't think I can get that (Behrens) paper either but, even i$f$ I could, I can't read German. (I guess it is German.) But I'll look at the other papers you've kindly provided.2014-07-13