Latin Square

An $n\times n$ Latin square is a Latin Rectangle with $k=n$. Specifically, a Latin square consists of $n$ sets of the numbers 1 to $n$ arranged in such a way that no orthogonal (row or column) contains the same two numbers. The numbers of Latin squares of order $n=1$, 2, ... are 1, 2, 12, 576, ... (Sloane's A002860). A pair of Latin squares is said to be orthogonal if the $n^2$ pairs formed by juxtaposing the two arrays are all distinct.

Two of the Latin squares of order 3 are

$$\left[{\matrix{3 & 2 & 1\cr 2 & 1 & 3\cr 1 & 3 & 2\cr}}\righ... ...left[{\matrix{2 & 3 & 1\cr 1 & 2 & 3\cr 3 & 1 & 2\cr}}\right],$$

which are orthogonal. Two of the 576 Latin squares of order 4 are

$$\left[{\matrix{1 & 2 & 3 & 4\cr 2 & 1 & 4 & 3\cr 3 & 4 & 1 &... ...r 3 & 4 & 1 & 2\cr 4 & 3 & 2 & 1\cr 2 & 1 & 4 & 3\cr}}\right].$$

A normalized, or reduced, Latin square is a Latin square with the first row and column given by $\{1, 2, \ldots, n\}$. General Formulas for the number of normalized Latin squares $L(n,n)$ are given by Nechvatal (1981), Gessel (1987), and Shao and Wei (1992). The total number of Latin squares of order $n$ can then be computed from

$$N(n,n)= n!(n-1)!L(n,n) = n!(n-1)! L(n-1,n).$$

The numbers of normalized Latin square of order $n=1$, 2, ..., are 1, 1, 1, 4, 56, 9408, ... (Sloane's A000315). McKay and Rogoyski (1995) give the number of normalized Latin Rectangles $L(k,n)$ for $n=1$, ..., 10, as well as estimates for $L(n,n)$ with $n=11$, 12, ..., 15.

$n$	$L(n,n)$
11	$5.36\times 10^{33}$
12	$1.62\times 10^{44}$
13	$2.51\times 10^{56}$
14	$2.33\times 10^{70}$
15	$1.5\times 10^{86}$

See also Euler Square, Kirkman Triple System, Partial Latin Square, Quasigroup

References

Colbourn, C. J. and Dinitz, J. H. CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, 1996.

Gessel, I. ``Counting Latin Rectangles.'' Bull. Amer. Math. Soc. 16, 79-83, 1987.

Hunter, J. A. H. and Madachy, J. S. Mathematical Diversions. New York: Dover, pp. 33-34, 1975.

Kraitchik, M. ``Latin Squares.'' §7.11 in Mathematical Recreations. New York: W. W. Norton, p. 178, 1942.

Lindner, C. C. and Rodger, C. A. Design Theory. Boca Raton, FL: CRC Press, 1997.

McKay, B. D. and Rogoyski, E. ``Latin Squares of Order 10.'' Electronic J. Combinatorics 2, N3 1-4, 1995. http://www.combinatorics.org/Volume_2/volume2.html#N3.

Nechvatal, J. R. ``Asymptotic Enumeration of Generalised Latin Rectangles.'' Util. Math. 20, 273-292, 1981.

Ryser, H. J. ``Latin Rectangles.'' §3.3 in Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 35-37, 1963.

Shao, J.-Y. and Wei, W.-D. ``A Formula for the Number of Latin Squares.'' Disc. Math. 110, 293-296, 1992.

Sloane, N. J. A. Sequences A002860/M2051 and A000315/M3690 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.