Formula for the number of latin squares of size $n$?

Is there a "easy to compute" formula for the number of Latin Squares or the number of reduced Latin squares of size $n$?

Solution 1:

When it comes down to it, there has only been one important step towards an "easy to compute" formula for $L_n$, the number of Latin squares of order $n$. This was by Sade:

A. A. Sade, Énumération des carrés latins, application au 7e ordre, conjecture pour les orders supérieurs, privately published, (1948). 8 pp.

Sade gave a method for non-constructive counting of Latin squares. More specifically, he clumped together Latin rectangles that have the same number of completions (as recognised by their "template"). Subsequent authors have merely implemented Sade's method on a computer...

For order 10:

B. D. McKay and E. Rogoyski, Latin squares of order ten, Electron. J. Combin., 2 (1995). N3, 4 pp.

For order 11:

B. D. McKay and I. M. Wanless, On the number of Latin squares, Ann. Comb., 9 (2005), pp. 335–344.

I discuss this in my survey paper and PhD thesis (both are open access).

I have often thought about performing the computation for $12 \times 12$ Latin squares, which would be a particularly ambitious project. The difference between $11 \times 11$ and $12 \times 12$ is huge. Here are some quotes which highlight the difficulty (here $R_n=n!(n-1)!L_n$):

McKay, Wanless (2005) write:

It is unlikely that $R_{12}$ will be computable by the same method for some time, since the number of regular bipartite graphs of order 24 and degree 6 is more than $10^{11}$.

Stones, Wanless (2012) (link) write:

McKay and Rogoyski and Kuznetsov gave $R_{12} \approx 1.62 \cdot 10^{44} > 3 \cdot 10^{10} \cdot R_{11}$... Barring the discovery of a faster algorithm, the evaluation of $R_{12}$ will remain infeasible for some years yet.

To me, it doesn't seem completely out-of-the-question to find $R_{12}$ within the next 30 or so years. It would require the use of some kind of supercomputer, and (presumably) a hybrid GPU-CPU implementation. However, the cost and effort required to do this would probably far exceed the benefit of finding $R_{12}$.

Estimates for the number of Latin squares of order $n$ are around, however, most recently by:

C. Zhang and J. Ma, Counting solutions for the N-queens and Latin square problems by Monte Carlo simulations, Phys. Rev. E, 79 (2009). 016703.

Other comments:

• There are several known bounds and congruences for $L_n$.
• There are many formulae for $L_n$ (which are impractical to use, but theoretically interesting).
• Counting $k \times n$ Latin rectangles, for fixed $k$, is theoretically "easy", since these number satisfy linear recurrences, as proved in:

I. M. Gessel, Counting Latin rectangles, Bull. Amer. Math. Soc. 16 (1) (1987) 79–83.

(see also Doyle's formula, which is currently the best way to count $k \times n$ Latin rectangle for $n \leq 6$.)

• I don't think it's possible to give a proper answer to the question: why is it hard to count Latin squares? It might be easy, and we haven't been clever enough yet. But the general idea as to why I think it is hard, is that, when constructing Latin squares, early decisions can affect the number of completions (and thus need to be accounted for in an enumeration). Compare to row-Latin squares ($n \times n$ matrices in which each symbol appears in every row, and we allow duplicates in columns). The number here is $n!^n$. Here, early decisions don't affect the number of completions.

Solution 2:

No - if there was then OEIS A002860 and A000315 would have a formula: instead it labels the calculation as hard.

The numbers have been calculated up to $n=11$ in McKay, B. D. and Wanless, I. M. "On the Number of Latin Squares." Ann. Combin. 9, 335-344, 2005 which you can read (with subscription) at Springer or (without) at arXiv.

Solution 3:

OEIS has a sequence of "number of Latin squares of order $n$, with references. But it's labeled "hard", and I think the numbers listed there are the only terms known.