TOPICS
Search

Latin Square


An n×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 number twice. For example, the two Latin squares of order two are given by

 [1 2; 2 1],[2 1; 1 2],
(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],
(2)

and two of the 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].
(3)
LatinSquareGraphs

Latin squares correspond to minimum vertex colorings of the n×n rook graph, which are illustrated above for n=2 and 3.

The numbers N(n,n) of Latin squares of order n=1, 2, ... are 1, 2, 12, 576, 161280, ... (OEIS A002860). The number L(n,n) of isotopically distinct Latin squares of order n=1, 2, ... are 1, 1, 1, 2, 2, 22, 564, 1676267, ... (OEIS A040082).

A pair of Latin squares is said to be orthogonal if the n^2 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]
(4)

are orthogonal. The number of pairs of orthogonal Latin squares of order n=1, 2, ... are 0, 0, 36, 3456, ... (OEIS A072377).

The number of Latin squares of order n with first row given by {1,2,...,n} is the same as the number of fixed diagonal Latin squares of order n (i.e., the number of Latin squares of order n having all 1s along their main diagonals). For n=1, 2, ..., the numbers of such matrices are 1, 1, 2, 24, 1344, 1128960, ... (OEIS A000479) and the total number of Latin squares of order n is equal to this number times n!.

A normalized, or reduced, Latin square is a Latin square with the first row and column given by {1,2,...,n}. General formulas for the number of normalized n×n Latin squares L(n,n) are given by Nechvatal (1981), Gessel (1987), and Shao and Wei (1992), but the asymptotic value of L(n,n) is not known (MacKay and Wanless 2005). The total number of Latin squares N(n,n) of order n can then be computed from

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

The numbers of normalized Latin squares of order n=1, 2, ..., are summarized in the following table (OEIS A000315).

nL(n,n)reference
11
21
31
44
556Euler (1782), Cayley (1890), MacMahon (1915; incorrect value)
69408Frolov (1890) and Tarry (1900)
716942080Frolov (1890; incorrect), Norton (1939; incomplete), Sade (1948), Saxena (1951)
8535281401856Wells (1967)
9377597570964258816Bammel and Rothstein (1975)
107580721483160132811489280McKay and Rogoyski (1995)
115363937773277371298119673540771840McKay and Wanless (2005)
121.62×10^(44)McKay and Rogoyski (1995)
132.51×10^(56)McKay and Rogoyski (1995)
142.33×10^(70)McKay and Rogoyski (1995)
151.5×10^(86)McKay and Rogoyski (1995)

Sudoku is a special case of a Latin square.


See also

36 Officer Problem, Alon-Tarsi Conjecture, Euler Square, Kirkman Triple System, Lam's Problem, Partial Latin Square, Quasigroup, Rook Graph, SOMA, Sudoku

Explore with Wolfram|Alpha

References

Bammel, S. E. and Rothstein, J. "The Number of 9×9 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. http://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.McKay, B. D. "Latin Squares." http://users.cecs.anu.edu.au/~bdm/data/latin.html.Nechvatal, J. R. "Asymptotic Enumeration of Generalised Latin Rectangles." Util. Math. 20, 273-292, 1981.Norton, H. W. "The 7×7 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 7×7 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.

Referenced on Wolfram|Alpha

Latin Square

Cite this as:

Weisstein, Eric W. "Latin Square." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LatinSquare.html

Subject classifications