Number of weak-sudoku tables

Question

We say that an $n\times n$ table of integers in $\{1,\dots,n\}$ has the weak-sudoku property if each number appears exactly once in each row and each column.

The main question is: how many weak-sudoku tables are there, depending on $n$?

Yet, this seems a quite unapproachable question, hence we can ask some hopefully easier questions such as:

• How does this number $\varphi(n)$ grow asymptotically?
• If we say that two tables are equivalent if we can obtain one from another by row and column permutations, and/or by operations on the table induced by permutations of $\{1,\dots , n\}$ (i.e. renaming the numbers in the table), how many equivalence classes $\varepsilon(n)$ are there?

Here are some observations:

• $\varphi(1)=1, \varphi(2)=2, \varphi(3)=12$
• $\varepsilon(1)=\varepsilon(2)=\varepsilon(3)=1, \varepsilon(4)=4, \varepsilon(5)=56, \varepsilon(6)=9408$

We observe that, numerically, it seems that $\varepsilon(n)\sim e^{(n-3)^2}$.

Moreover we can identify some canonical representatives for the equivalence classes that are the weak-sudoku tables of the form below: $$ \begin{pmatrix} 1& 2 & 3& \cdots & n\\ *& 1 & *& \cdots& *\\ *&* & 1 & \cdots&*\\ \vdots& \vdots&\vdots & \ddots& \vdots\\ *& *&*&\cdots&1 \end{pmatrix} $$

By this canonical form we can implement an Octave function that calculates $\varepsilon(n)$ by which we have calculated the above values of $\varepsilon$.

A=diag(ones(1,n));
A(2:end,1)=2:j;

function count=table(A,count)
count=0;
n=size(A)(1);
if((A==0)==A*0)
 A;
 count=count+1;
 return 
endif
[i,j]=find(A==0);
i=i(1);
j=j(1);
for k=2:n
 if (all([A(i,:);A(:,j)']!=k))
   B=A;
   B(i,j)=k;
   count=count+table(B);
 endif
endfor
end

Finally we also observe that $\varphi(n)\leq (n!)^2\varepsilon(n)$ and that therefore, if the above estimation is correct, $\varphi(n)\sim \varepsilon(n)$.

Answer 1

Your table is known as a Latin square. According to Wikipedia, there are no good estimates for the number of Latin squares. The OEIS contains some counts for $n \leq 11$: A002860. In particular, for $n = 9$ the answer is 5524751496156892842531225600.