Enumeration of Latin Squares and Rectangles
From Combinatorics Wiki
Author's note: This is currently a snippet from my PhD thesis On the number of Latin rectangles^{[1]} and the paper The many formulae for the number of Latin rectangles^{[2]}. I can be contacted by email: douglas.stones (at) sci.monash.edu.au
- Douglas S. Stones
Contents |
Introduction
A Latin rectangle is a array L = (l_{ij}) of n symbols such that each symbol occurs exactly once in each row and at most once in each column. If k = n then L is called a Latin square^{[3]}. A Latin rectangle on the symbols is called normalised if the first row is and called reduced if the first row is and the first column is . Let L_{k,n} denote the number of Latin rectangles, K_{k,n} denote the number of normalised Latin rectangles and let R_{k,n} denote the number of reduced Latin rectangles.. The total number of Latin rectangles is . In the case of Latin squares, the numbers L_{n,n}, K_{n,n} and R_{n,n} shall be denoted L_{n}, K_{n} and R_{n} respectively.
The values of R_{k,n} for were given by McKay and Wanless ^{[4]}, which we reproduce below. We omit R_{1,n} = 1. Sloane's ^{[5]} A002860 lists K_{n}.
n = 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|
k = 2 | 1 | 1 | 3 | 11 | 53 | |||
3 | 1 | 2^{2} | ||||||
4 | 2^{2} | |||||||
5 | ||||||||
6 | ||||||||
7 | ||||||||
8 | ||||||||
9 |
n = 10 | n = 11 | |
---|---|---|
k = 2 | 1468457 | |
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | ||
9 | ||
10 | ||
11 |
The enumeration of R_{n} has a history stretching back to Euler^{[6]}, Cayley^{[7]} and MacMahon^{[8]}^{[9]}. A survey is provided by McKay, Meynert and Myrvold^{[10]}. An upper bound on R_{n} are obtained through the study of permanents^{[11]}^{[12]}. A lower bound on R_{n} is given by van Lint and Wilson^{[13]}. Estimates for the number of Latin squares were given by McKay and Rogoyski^{[14]}, Zhang and Ma^{[15]} and Kuznetsov^{[16]}.
A survey of the enumeration of Latin rectangles was given by Stones and Wanless. An asymptotic formula for the number of Latin rectangles was given by Goldsil and McKay^{[17]} as with k = o(n^{6 / 7}). The value of K_{2,n}, K_{3,n} and K_{4,n} is given by Sloane's A000166^{[18]}, A000186^{[19]} and A000573^{[20]}, respectively.
Bailey and Cameron^{[21]} (see also the CRC Handbook^{[22]}) discuss combinatorial objects equivalent to Latin squares. Wikipedia host a list of problems in the theory of Latin squares^{[23]}.
The number D_{n} of derangements^{[24]} is related to the number of Latin rectangles by
Riordan^{[25]} gave the credit to Yamamoto for the equation
Let p be a prime. Stones and Wanless showed that if and then R_{k,n + p} is divisible by p if and only if R_{k,n} is divisible by p. For example, in the following table we can see that R_{4,n} is indivisible by 5 for all . Furthermore, if p < k then divides R_{k,n}. We will inspect the divisors of R_{4,n}, R_{5,n} and R_{6,n} in the following sections.
Four-line Latin rectangles
A formula for the number of reduced Latin rectangles is given by Doyle, from which the following table of values of R_{4,n} was calculated. The c code used has been uploaded to Google Code^{[26]} along with code for R_{5,n} and R_{6,n}. We use p_{m} to denote an m-digit prime number and c_{m} to denote an m-digit composite number. Factorisations were performed using Dario Alpern's applet^{[27]}. Other formulae for the number of four-line Latin rectangles are given by Light Jr.^{[28]}, Athreya, Pranesachar and Singhi^{[29]} (see also Pranesachar^{[30]}) and Gessel^{[31]}. A similar claim is made by de Gennaro^{[32]}.
n | R_{4,n} |
---|---|
4 | 2^{2} |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 | |
29 | |
30 | |
31 | |
32 | |
33 | |
34 | |
35 | |
36 | |
37 | |
38 | |
39 | |
40 | |
41 | |
42 | |
43 | |
44 | |
45 | |
46 | |
47 | |
48 | |
49 | |
50 | |
51 | |
52 | |
53 | |
54 | |
55 | |
56 | |
57 | |
58 | |
59 | |
60 | |
61 | |
62 | |
63 | |
64 | |
65 | |
66 | |
67 | |
68 | |
69 | |
70 | |
71 | |
72 | |
73 | |
74 | |
75 | |
76 | |
77 | |
78 | |
79 | |
80 |
Five-line Latin rectangles
Doyle's method can be adapted to also find R_{5,n}, from which the following table was calculated.
n | R_{5,n} |
---|---|
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 |
Six-line Latin rectangles
Doyle's method can be adapted to also find R_{6,n}, from which the following table was calculated.
n | R_{6,n} |
---|---|
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 |
Notes
- ↑ D. S. Stones, On the number of Latin rectangles, Ph.D. thesis, Monash University, 2010. [1]
- ↑ D. S. Stones, The many formulae for the number of Latin rectangles. Electron. J. Combin., 17 (2010), A1. [2]
- ↑ http://en.wikipedia.org/wiki/Latin_square
- ↑ B. D. McKay, I. M. Wanless, On the number of Latin squares, Ann. Comb. 9 (2005) 335--344.
- ↑ N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://www.research.att.com/~njas/sequences/A002860
- ↑ L. Euler, Recherches sur une nouvelle espéce de quarrés magiques, Verh. Zeeuwsch. Gennot. Weten. Vliss. 9 (1782) 85--239, Eneström E530, Opera Omnia OI7, 291--392.
- ↑ A. Cayley, On Latin squares, Messenger of Math., 19 (1890) 135--137.
- ↑ P. A. MacMahon, A new method in combinatory analysis, with applications to Latin squares and associated questions, Trans. Camb. Phil. Soc., 16 (1898) 262--290.
- ↑ P. A. MacMahon, Combinatory Analysis, Chelsea, 1960.
- ↑ B. D. McKay, A. Meynert, and W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007) 98--119.
- ↑ H. Minc, Permanents, Addison-Wesley, 1978. Encyclopedia of Mathematics and its Applications, volume 6.
- ↑ L. M. Brègman, Certain properties of nonnegative matrices and their permanents, Soviet Math. Dokl., 14 (1973) 945--949. Dokl. Akad. Nauk SSSR 211 (1973) 27--30.
- ↑ J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.
- ↑ B. D. McKay and E. Rogoyski, Latin squares of order ten, Electron. J. Combin., 2 (1995) N3, 4 pp. http://www.combinatorics.org/Volume_2/PDFFiles/v2i1n3.pdf
- ↑ C. Zhang and J. Ma, Counting solutions for the N-queens and Latin square problems by efficient Monte Carlo simulations, Phys. Rev. E, 79 (2009), 016703.
- ↑ N. Y. Kuznetsov, Estimating the number of Latin rectangles by the fast simulation method, Cybernet. Systems Anal., 45 (2009) 69--75.
- ↑ C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, Bull. Amer. Math. Soc. (N.S.) 10 (1984) 91--92.
- ↑ http://www.research.att.com/~njas/sequences/A000166
- ↑ http://www.research.att.com/~njas/sequences/A000186
- ↑ http://www.research.att.com/~njas/sequences/A000573
- ↑ R. A. Bailey and P. J. Cameron, Latin squares: Equivalences and equivalents, (2003). Encyclopedia of Design Theory. http://designtheory.org/library/encyc/topics/lsee.pdf
- ↑ C. J. Colbourn, J. H. Dinitz, et al., The CRC Handbook of Combinatorial Designs, CRC Press, 1996.
- ↑ http://en.wikipedia.org/wiki/Problems_in_Latin_squares
- ↑ http://en.wikipedia.org/wiki/Derangement
- ↑ J. Riordan, A recurrence relation for three-line Latin rectangles, Amer. Math. Monthly 59 (3) (1952) 159-162.
- ↑ http://code.google.com/p/latinrectangles/downloads/list
- ↑ http://www.alpertron.com.ar/ECM.HTM
- ↑ F. W. Light, Jr, A procedure for the enumeration of Latin rectangles, Fibonacci Quart., 11 (1973) 241-246.
- ↑ K. B. Athreya, C. R. Pranesachar, and N. M. Singhi, On the number of Latin rectangles and chromatic polynomial of L(K_{r,s}), European J. Combin., 1 (1980) 9-17.
- ↑ C. R. Pranesachar, Enumeration of Latin rectangles via SDR's, in Combinatorics and Graph Theory, A. Dold, B. Eckmann, and S. B. Rao, eds., Springer, 1981, 380-390.
- ↑ I. M. Gessel, Counting Latin rectangles, Bull. Amer. Math. Soc., 16 (1987), 79-83.
- ↑ A. de Gennaro, How many Latin rectangles are there?, (2007). arXiv:0711.0527v1 [math.CO], 20 pp. http://arxiv.org/abs/0711.0527
References
- J. Denés and A. D. Keedwell, Latin Squares and their Applications, Academic Press, 1974.
- J. Denés and A. D. Keedwell, Latin Squares: New Developments in the Theory and Applications, North-Holland, Amsterdam, 1991.
- P. G. Doyle, The number of Latin rectangles, (2007). arXiv:math/0703896v1 [math.CO], 15 pp. http://arxiv1.library.cornell.edu/abs/math/0703896v1
- D. S. Stones and I. M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A., 117 (2010), pp. 204-215.