Latin Square
An 
Latin square is a Latin
rectangle with 
. Specifically, a Latin square consists
of 
sets of the numbers 1 to 
arranged in such
a way that no orthogonal (row or column) contains the same number twice. For example,
the two Latin squares of order two are given by
![[1 2; 2 1],[2 1; 1 2],](/images/equations/LatinSquare/NumberedEquation1.gif) |
(1)
|
the 12 Latin squares of order three are given by
![[1 2 3; 2 3 1; 3 1 2],[1 2 3; 3 1 2; 2 3 1],[1 3 2; 2 1 3; 3 2 1],[1 3 2; 3 2 1; 2 1 3],
[2 1 3; 1 3 2; 3 2 1],[2 1 3; 3 2 1; 1 3 2],[2 3 1; 1 2 3; 3 1 2],[2 3 1; 3 1 2; 1 2 3],
[3 2 1; 1 3 2; 2 1 3],[3 2 1; 2 1 3; 1 3 2],[3 1 2; 1 2 3; 2 3 1],[3 1 2; 2 3 1; 1 2 3],](/images/equations/LatinSquare/NumberedEquation2.gif) |
(2)
|
and two of the whopping 576 Latin squares of order 4 are given by
![[1 2 3 4; 2 1 4 3; 3 4 1 2; 4 3 2 1] and [1 2 3 4; 3 4 1 2; 4 3 2 1; 2 1 4 3].](/images/equations/LatinSquare/NumberedEquation3.gif) |
(3)
|
The numbers 
of Latin squares of order 
, 2, ... are 1, 2, 12, 576, 161280, ... (OEIS
A002860). The number 
of isotopically
distinct Latin squares of order 
, 2, ... are
1, 1, 1, 2, 2, 22, 564, 1676267, ... (OEIS A040082).
A pair of Latin squares is said to be orthogonal if the 
pairs formed
by juxtaposing the two arrays are all distinct. For example, the two Latin squares
![[3 2 1; 2 1 3; 1 3 2] [2 3 1; 1 2 3; 3 1 2]](/images/equations/LatinSquare/NumberedEquation4.gif) |
(4)
|
are orthogonal. The number of pairs of orthogonal Latin squares of order 
, 2, ... are
0, 0, 36, 3456, ... (OEIS A072377).
The number of Latin squares of order 
with first row
given by 
is the same as the number
of fixed diagonal Latin squares of order 
(i.e., the number
of Latin squares of order 
having all 1s along their main diagonals).
For 
, 2, ..., the numbers of such matrices are 1,
1, 2, 24, 1344, 1128960, ... (OEIS A000479)
and the total number of Latin squares of order 
is equal to this
number times 
.
A normalized, or reduced, Latin square is a Latin square with the first row and column given by 
. General formulas
for the number of normalized 
Latin squares
are given by Nechvatal (1981), Gessel (1987),
and Shao and Wei (1992), but the asymptotic value of 
is not known
(MacKay and Wanless 2005). The total number of Latin squares 
of order
can then be computed from
 |
(5)
|
The numbers of normalized Latin squares of order 
, 2, ..., are
summarized in the following table (OEIS A000315).
 |  | reference |
| 1 | 1 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 4 | |
| 5 | 56 | Euler (1782), Cayley (1890), MacMahon (1915; incorrect value) |
| 6 | 9408 | Frolov (1890) and Tarry (1900) |
| 7 | 16942080 | Frolov (1890; incorrect), Norton (1939; incomplete), Sade (1948), Saxena (1951) |
| 8 | 535281401856 | Wells (1967) |
| 9 | 377597570964258816 | Bammel and Rothstein (1975) |
| 10 | 7580721483160132811489280 | McKay and Rogoyski (1995) |
| 11 | 5363937773277371298119673540771840 | McKay and Wanless (2005) |
| 12 |  | McKay and Rogoyski (1995) |
| 13 |  | McKay and Rogoyski (1995) |
| 14 |  | McKay and Rogoyski (1995) |
| 15 |  | McKay and Rogoyski (1995) |
Sudoku is a special case of a Latin square.
Bammel, S. E. and Rothstein, J. "The Number of 
Latin Squares."
Disc. Math. 11, 93-95, 1975.
Cayley, A. "On Latin Squares." Oxford Cambridge Dublin Messenger Math. 19, 135-137, 1890.
Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, 1996.
Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 183, 1974.
Euler, L. "Recherches sur une nouvelle esp ece de quarrès magiques." Verh. Zeeuwsch Gennot. Weten Vliss 9, 85-239, 1782.
Frolov, M. "Sur les permutations carrés." J. de Math. spéc. 4, 8-11 and 25-30, 1890.
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.
MacMahon, P. A. Combinatory Analysis, Vol. 1. London: Cambridge University Press, 1915.
McKay, B. D. and Rogoyski, E. "Latin Squares of Order 10." Electronic J. Combinatorics 2, No. 1, R3, 1-4, 1995. https://www.combinatorics.org/Volume_2/Abstracts/v2i1r3.html.
McKay, B. D. and Wanless, I. M. "On the Number of Latin Squares." Ann. Combin. 9, 335-344, 2005.
Nechvatal, J. R. "Asymptotic Enumeration of Generalised Latin Rectangles." Util. Math. 20, 273-292, 1981.
Norton, H. W. "The 
Squares."
Ann. Eugenics 9, 269-307, 1939.
Rohl, J. S. Recursion via Pascal. Cambridge, England: Cambridge University Press, pp. 162-165, 1984.
Ryser, H. J. "Latin Rectangles." §3.3 in Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 35-37, 1963.
Sade, A. "Enumération des carrés latins. Application au 7ème ordre. Conjectures pour les ordres supérieurs." 8 pp. Marseille, France: Privately published, 1948.
Saxena, P. N. "A Simplified Method of Enumerating Latin Squares by MacMahon's Differential Operators; II. The 
Latin Squares."
J. Indian Soc. Agricultural Statist. 3, 24-79, 1951.
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 A000479, A002860/M2051, A000315/M3690, A040082, and A072377 in "The On-Line Encyclopedia of Integer Sequences."
Tarry, G. "Le problème de 36 officiers." Compte Rendu de l'Assoc. Français Avanc. Sci. Naturel 1, 122-123, 1900.
Tarry, G. "Le problème de 36 officiers." Compte Rendu de l'Assoc. Français Avanc. Sci. Naturel 2, 170-203, 1901.
Wells, M. B. "The Number of Latin Squares of Order Eight." J. Combin. Th. 3, 98-99, 1967.
Weisstein, Eric W. "Latin Square." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LatinSquare.html
Contact the MathWorld Team
latin square
