Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

3 Answers 3

up vote 3 down vote accepted

These are called "equi-n-squares."

share|improve this answer

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.

share|improve this answer
    
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.)

share|improve this answer
    
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 at 6:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.