Enumeration of Latin Squares and Rectangles

From Combinatorics Wiki

Jump to: navigation, search

Author's note: This is currently a snippet from my PhD thesis On the number of Latin rectangles (submitted). I can be contacted by email: douglas.stones (at) sci.monash.edu.au

- Douglas S. Stones


Contents

Introduction

A k \times n Latin rectangle is a k \times n array L = (lij) 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[1]. A Latin rectangle on the symbols \mathbb{Z}_n is called normalised if the first row is (0,1, \dots, n-1) and called reduced if the first row is (0,1, \dots, n-1) and the first column is (0,1, \dots ,k-1)^T. Let Lk,n denote the number of k \times n Latin rectangles, Kk,n denote the number of k \times n normalised Latin rectangles and let Rk,n denote the number of reduced k \times n Latin rectangles.. The total number of k \times n Latin rectangles is L_{k,n}=n! K_{k,n} = \frac{n! (n-1)!} {(n-k)!} R_{k,n}. In the case of Latin squares, the numbers Ln,n, Kn,n and Rn,n shall be denoted Ln, Kn and Rn respectively.

The values of Rk,n for 1 \leq k \leq n \leq 11 were given by McKay and Wanless [2], which we reproduce below. We omit R1,n = 1. Sloane's [3] A002860 lists Kn.

n = 2 3 4 5 6 7 8 9
k = 2 1 1 3 11 53 3 \!\cdot\! 103 13 \!\cdot\! 163 11 \!\cdot\! 37 \!\cdot\! 41
3 1 22 2 \!\cdot\! 23 2^3 \!\cdot\! 7 \!\cdot\! 19 2^4 \!\cdot\! 2237 2^6 \!\cdot\! 26153 2^5 \!\cdot\! 13 \!\cdot\! 167 \!\cdot\! 1489
4 22 2^3 \!\cdot\! 7 2^3 \!\cdot\! 3^2 \!\cdot\! 7 \!\cdot\! 13 2^5 \!\cdot\! 3 \!\cdot\! 19 \!\cdot\! 709 2^6 \!\cdot\! 3 \!\cdot\! 159 \!\cdot\! 14713 2^7 \!\cdot\! 3^4 \!\cdot\! 20025517
5 2^3 \!\cdot\! 7 2^6 \!\cdot\! 3 \!\cdot\! 7^2 2^8 \!\cdot\! 3 \!\cdot\! 5^2 \!\cdot\! 587 2^{11} \!\cdot\! 3 \!\cdot\! 23 \!\cdot\! 192529 2^{11} \!\cdot\! 3^4 \!\cdot\! 13 \!\cdot\! 52251029
6 2^6 \!\cdot\! 3 \!\cdot\! 7^2 2^{10} \!\cdot\! 3 \!\cdot\! 5 \!\cdot\! 1103 2^{11} \!\cdot\! 3 \!\cdot\! 7 \!\cdot\! 173 \!\cdot\! 45077 2^{14} \!\cdot\! 3^5 \!\cdot\! 3253351007
7 2^{10} \!\cdot\! 3 \!\cdot\! 5 \!\cdot\! 1103 2^{17} \!\cdot\! 3 \!\cdot\! 1361291 2^{15} \!\cdot\! 3^2 \!\cdot\! 61 \!\cdot\! 12923 \!\cdot\! 965171
8 2^{17} \!\cdot\! 3 \!\cdot\! 1361291 2^{21} \!\cdot\! 3^2 \!\cdot\! 5231 \!\cdot\! 3824477
9 2^{21} \!\cdot\! 3^2 \!\cdot\! 5231 \!\cdot\! 3824477
n = 10 n = 11
k = 2 3^2 \!\cdot\! 16481 1468457
3 2^6 \!\cdot\! 23 \!\cdot\! 61 \!\cdot\! 90821 2^7 \!\cdot\! 13 \!\cdot\! 23 \!\cdot\! 20851549
4 2^8 \!\cdot\! 3^3 \!\cdot\! 71 \!\cdot\! 271 \!\cdot\! 1106627 2^{10} \!\cdot\! 3^2 \!\cdot\! 1823 \!\cdot\! 8569184461
5 2^{16} \!\cdot\! 3^6 \!\cdot\! 19 \!\cdot\! 97 \!\cdot\! 8483617 2^{13} \!\cdot\! 3^2 \!\cdot\! 29 \!\cdot\! 168293 \!\cdot\! 20936295857
6 2^{14} \!\cdot\! 3^3 \!\cdot\! 5 \!\cdot\! 26053 \!\cdot\! 15110358097 2^{17} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 31 \!\cdot\! 2334139 \!\cdot\! 225638611943
7 2^{20} \!\cdot\! 3^3 \!\cdot\! 5 \!\cdot\! 509 \!\cdot\! 2458531126109 2^{21} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 9437 \!\cdot\! 269623520098467133
8 2^{21} \!\cdot\! 3^3 \!\cdot\! 5 \!\cdot\! 11 \!\cdot\! 13^2 \!\cdot\! 37 \!\cdot\! 1381 \!\cdot\! 159597187 2^{28} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 97 \!\cdot\! 73488673152815765447
9 2^{28} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 31 \!\cdot\! 37 \!\cdot\! 1468457 \!\cdot\! 547135293937 2^{32} \!\cdot\! 3^3 \!\cdot\! 5 \!\cdot\! 61 \!\cdot\! 7487 \!\cdot\! 260951 \!\cdot\! 42053669617
10 2^{28} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 31 \!\cdot\! 37 \!\cdot\! 1468457 \!\cdot\! 547135293937 2^{35} \!\cdot\! 3^4 \!\cdot\! 5 \!\cdot\! 2801 \!\cdot\! 2206499 \!\cdot\! 62368028479
11 2^{35} \!\cdot\! 3^4 \!\cdot\! 5 \!\cdot\! 2801 \!\cdot\! 2206499 \!\cdot\! 62368028479

The enumeration of Rn has a history stretching back to Euler[4], Cayley[5] and MacMahon[6][7]. A survey is provided by McKay, Meynert and Myrvold[8]. An upper bound on Rn are obtained through the study of permanents[9][10]. A lower bound on Rn is given by van Lint and Wilson[11]. Estimates for the number of Latin squares were given by McKay and Rogoyski[12], Zhang and Ma[13] and Kuznetsov[14].

A survey of the enumeration of Latin rectangles was given by Stones and Wanless. An asymptotic formula for the number of k \times n Latin rectangles was given by Goldsil and McKay[15] as n \rightarrow \infty with k = o(n6 / 7). The value of K2,n, K3,n and K4,n is given by Sloane's A000166[16], A000186[17] and A000573[18], respectively.

Bailey and Cameron[19] (see also the CRC Handbook[20]) discuss combinatorial objects equivalent to Latin squares. Wikipedia host a list of problems in the theory of Latin squares[21].

The number Dn of derangements[22] is related to the number of 2 \times n Latin rectangles by

D_n = n! \sum_{i=0}^n \frac{(-1)^i}{i!} = K_{2,n} = (n-1) R_{2,n} .

Riordan[23] gave the credit to Yamamoto for the equation

R_{3,n}= \sum_{i+j+k=n} n (n-3)! (-1)^j \frac{2^k i!}{k!} {{3i+j+2} \choose {j}} .

Let p be a prime. Stones and Wanless showed that if k \leq n and p \geq k then Rk,n + p is divisible by p if and only if Rk,n is divisible by p. For example, in the following table we can see that R4,n is indivisible by 5 for all n \geq 4. Furthermore, if p < k then p^{\left\lfloor (n-k)/p \right\rfloor} divides Rk,n. We will inspect the divisors of R4,n, R5,n and R6,n in the following sections.

Four-line Latin rectangles

A formula for the number of reduced 4 \times n Latin rectangles is given by Doyle, from which the following table of values of R4,n was calculated. The c code used has been uploaded to Google Code[24] along with code for R5,n and R6,n. We use pm to denote an m-digit prime number and cm to denote an m-digit composite number. Factorisations were performed using Dario Alpern's applet[25]. Other formulae for the number of four-line Latin rectangles are given by Light Jr.[26], Athreya, Pranesachar and Singhi[27] (see also Pranesachar[28]) and Gessel[29]. A similar claim is made by de Gennaro[30].

n R4,n
4 22
5 2^3 \cdot 7
6 2^3 \cdot 3^2 \cdot 7 \cdot 13
7 2^5 \cdot 3 \cdot 19 \cdot 709
8 2^6 \cdot 3 \cdot 149 \cdot 14713
9 2^7 \cdot 3^4 \cdot 20025517
10 2^8 \cdot 3^3 \cdot 71 \cdot 271 \cdot 1106627
11 2^{10} \cdot 3^2 \cdot 1823 \cdot 8569184461
12 2^9 \cdot 3^3 \cdot 7 \cdot 1945245990285863
13 2^{10} \cdot 3^4 \cdot 7 \cdot 587 \cdot 50821 \cdot 18504497761
14 2^{10} \cdot 3^4 \cdot 8384657190246053351461
15 2^{12} \cdot 3^5 \cdot 30525787 \cdot 62144400106703441
16 2^{14} \cdot 3^5 \cdot 2693 \cdot 42787 \cdot 1699482467 \cdot 8098773443
17 2^{16} \cdot 3^5 \cdot 131 \cdot 271 \cdot 17104781 \cdot 166337753 \cdot 15949178369
18 2^{14} \cdot 3^7 \cdot 23 \cdot 61 \cdot 3938593 \cdot 632073448679498674606517
19 2^{17} \cdot 3^6 \cdot 7 \cdot 13 \cdot 61 \cdot 197007401 \cdot 158435451761 \cdot 43809270413057
20 2^{17} \cdot 3^6 \cdot 7^2 \cdot 1056529591513682816198269594516734004747
21 2^{18} \cdot 3^7 \cdot 19 \cdot 31253 \cdot 103657 \cdot 1115736555797150985616406088863209
22 2^{18} \cdot 3^8 \cdot 158419 \cdot 366314603941483807 \cdot 3636463205495 660670300697
23 2^{20} \cdot 3^8 \cdot 58309 \cdot 1588208779694954759917 \cdot 6040665277134180218
24 2^{21} \cdot 3^9 \cdot 43 \cdot 283 \cdot 1373 \cdot 8191 \cdot 297652680582511 \cdot 27741149414473864785280935767
25 2^{22} \cdot 3^{11} \cdot 1938799914572671 \cdot 446065653297963631389971651136461400611927
26 2^{23} \cdot 3^9 \cdot 7 \cdot 19 \cdot 31 \cdot 5147 \cdot 694758890407 \cdot 4111097244170498224110627242779017943828829
27 2^{25} \cdot 3^{12} \cdot 7 \cdot 13127 \cdot 107027245883591876663734983579930090734219751042699442932337
28 2^{24} \cdot 3^{10} \cdot 2971 \cdot 289193 \cdot 119778654930498126781085485573 \cdot 33763646513110549304820504221579
29 2^{25} \cdot 3^{18} \cdot 89 \cdot 340127 \cdot 14664589 \cdot 708047148584881433 \cdot 18446448103698226834842515812120539757
30 2^{25} \cdot 3^{11} \cdot 53 \cdot 665108490075366816004739 \cdot 49263632160401672471995001 \cdot 177657272104447390753874983
31 2^{27} \cdot 3^{13} \cdot 191 \cdot 17107 \cdot 3372357179039503 \cdot 39341724144469051 \cdot p_{42}
32 2^{30} \cdot 3^{13} \cdot 13 \cdot 9187 \cdot 1598924119669 \cdot 1193092186665238350705569 \cdot p_{43}
33 2^{30} \cdot 3^{14} \cdot 7 \cdot 107 \cdot 235091 \cdot 1739471 \cdot 113684579977 \cdot p_{63}
34 2^{29} \cdot 3^{14} \cdot 7 \cdot 984125327 \cdot 34484685817 \cdot 128194091089 \cdot 142425115373 \cdot p_{51}
35 2^{32} \cdot 3^{14} \cdot 89 \cdot 97 \cdot 277 \cdot 205913 \cdot 1806011 \cdot 10254522251 \cdot p_{69}
36 2^{33} \cdot 3^{17} \cdot 53 \cdot 79 \cdot 9643 \cdot 667817 \cdot 24845207 \cdot 1038121669661 \cdot 2591875282769 \cdot 47741350809599 \cdot p_{18} \cdot p_{23}
37 2^{34} \cdot 3^{15} \cdot 41^2 \cdot c_{102}
38 2^{34} \cdot 3^{15} \cdot 401 \cdot 18773 \cdot p_{103}
39 2^{36} \cdot 3^{16} \cdot 61 \cdot 233 \cdot 45970356053 \cdot p_{99}
40 2^{37} \cdot 3^{18} \cdot 7 \cdot 19 \cdot 25463 \cdot c_{111}
41 2^{38} \cdot 3^{18} \cdot 7 \cdot 23 \cdot 193 \cdot p_{117}
42 2^{40} \cdot 3^{18} \cdot 5849 \cdot 167531523576421 \cdot 82776608090464507 \cdot 139777247474022707559098449 \cdot p_{65}
43 2^{41} \cdot 3^{18} \cdot 47 \cdot 709 \cdot 164993729 \cdot 2020013984903 \cdot 3068846736626420972569 \cdot p_{84}
44 2^{40} \cdot 3^{19} \cdot 89 \cdot 1883586157 \cdot c_{124}
45 2^{41} \cdot 3^{20} \cdot 13 \cdot 19 \cdot 834257923 \cdot c_{128}
46 2^{41} \cdot 3^{19} \cdot 283 \cdot c_{142}
47 2^{43} \cdot 3^{19} \cdot 7 \cdot 367 \cdot c_{146}
48 2^{45} \cdot 3^{21} \cdot 7 \cdot 20549 \cdot p_{147}
49 2^{47} \cdot 3^{22} \cdot p_{157}
50 2^{45} \cdot 3^{22} \cdot 59 \cdot 5519 \cdot 28609635239831 \cdot c_{143}
51 2^{48} \cdot 3^{23} \cdot 101 \cdot 683 \cdot 31069 \cdot c_{157}
52 2^{48} \cdot 3^{23} \cdot c_{171}
53 2^{49} \cdot 3^{23} \cdot 582632161 \cdot c_{167}
54 2^{49} \cdot 3^{25} \cdot 7 \cdot 79 \cdot 70207 \cdot c_{173}
55 2^{51} \cdot 3^{24} \cdot 7 \cdot 59 \cdot 127 \cdot c_{180}
56 2^{52} \cdot 3^{24} \cdot 1107194333513 \cdot 12777474733913023 \cdot c_{162}
57 2^{53} \cdot 3^{25} \cdot 31 \cdot 210173 \cdot 303283 \cdot 70679587751 \cdot p_{171}
58 2^{54} \cdot 3^{26} \cdot 13^2 \cdot 1733 \cdot 70657 \cdot 1597931 \cdot 165080147 \cdot 210722797 \cdot c_{166}
59 2^{56} \cdot 3^{26} \cdot 19 \cdot 1327 \cdot 548143835976602941553 \cdot c_{179}
60 2^{55} \cdot 3^{29} \cdot 263 \cdot 44203 \cdot 21803857 \cdot 3527424997 \cdot c_{184}
61 2^{56} \cdot 3^{27} \cdot 7 \cdot 1871 \cdot 5039 \cdot 12421 \cdot c_{202}
62 2^{56} \cdot 3^{27} \cdot 7 \cdot 151 \cdot 2953 \cdot 28111 \cdot 489239 \cdot 76373981 \cdot 163272563 \cdot 1971081834929 \cdot c_{174}
63 2^{58} \cdot 3^{30} \cdot 151 \cdot 213481 \cdot 1972121 \cdot 75421221701351 \cdot c_{195}
64 2^{62} \cdot 3^{30} \cdot 19 \cdot 23 \cdot p_{224}
65 2^{61} \cdot 3^{28} \cdot 304979 \cdot 12268693 \cdot 10203301555231523 \cdot c_{205}
66 2^{60} \cdot 3^{29} \cdot 2501881 \cdot 240510791 \cdot 516984175115077 \cdot c_{209}
67 2^{63} \cdot 3^{30} \cdot 43 \cdot 439 \cdot 752903 \cdot 1923479 \cdot 728432144959 \cdot c_{215}
68 2^{65} \cdot 3^{30} \cdot 7 \cdot c_{247}
69 2^{66} \cdot 3^{31} \cdot 7^2 \cdot 7547 \cdot c_{247}
70 2^{66} \cdot 3^{31} \cdot 599 \cdot 2571712749467 \cdot 11054971806915961 \cdot c_{227}
71 2^{68} \cdot 3^{31} \cdot 13 \cdot 257 \cdot c_{259}
72 2^{69} \cdot 3^{33} \cdot 157 \cdot 419 \cdot 677 \cdot 291701 \cdot 479881 \cdot c_{248}
73 2^{70} \cdot 3^{32} \cdot 79 \cdot 1031 \cdot 137567 \cdot 6462531289 \cdot c_{253}
74 2^{76} \cdot 3^{32} \cdot 2053 \cdot c_{273}
75 2^{73} \cdot 3^{33} \cdot 7 \cdot 599693 \cdot 67430864099 \cdot c_{265}
76 2^{72} \cdot 3^{34} \cdot 7 \cdot 47242055647 \cdot c_{277}
77 2^{73} \cdot 3^{34} \cdot 541 \cdot 593 \cdot c_{288}
78 2^{73} \cdot 3^{35} \cdot 19 \cdot 41 \cdot c_{296}
79 2^{75} \cdot 3^{36} \cdot 61 \cdot 509 \cdot 11959 \cdot 1281392093 \cdot 1764618464359 \cdot 9445461309983 \cdot c_{260}
80 2^{77} \cdot 3^{35} \cdot 61 \cdot 67751 \cdot 173775997 \cdot c_{294}

Five-line Latin rectangles

Doyle's method can be adapted to also find R5,n, from which the following table was calculated.

n R5,n
5 2^3 \cdot 7
6 2^6 \cdot 3 \cdot 7^2
7 2^8 \cdot 3 \cdot 5^2 \cdot 587
8 2^{11} \cdot 3 \cdot 23 \cdot 192529
9 2^{11} \cdot 3^4 \cdot 13 \cdot 52251029
10 2^{16} \cdot 3^6 \cdot 19 \cdot 97 \cdot 8483617
11 2^{13} \cdot 3^2 \cdot 29 \cdot 168293 \cdot 20936295857
12 2^{17} \cdot 3^6 \cdot 5 \cdot 7 \cdot 47 \cdot 59 \cdot 313 \cdot 38257310467
13 2^{19} \cdot 3^3 \cdot 7 \cdot 23364884851571662672051
14 2^{27} \cdot 3^4 \cdot 101 \cdot 449 \cdot 1039 \cdot 3019 \cdot 22811 \cdot 1882698637
15 2^{22} \cdot 3^7 \cdot 19 \cdot 423843896863 \cdot 34662016427839511
16 2^{28} \cdot 3^6 \cdot 3604099 \cdot 40721862001 \cdot 4526515223205743
17 2^{25} \cdot 3^5 \cdot 5 \cdot 15001087 \cdot 13964976140347893908947110110827
18 2^{28} \cdot 3^9 \cdot 1019173084339 \cdot 237316919875331 \cdot 559319730817259
19 2^{28} \cdot 3^6 \cdot 7 \cdot 47 \cdot 149 \cdot 532451 \cdot 347100904121707 \cdot 42395531645181804688477
20 2^{32} \cdot 3^9 \cdot 7 \cdot 67 \cdot 163 \cdot 360046981713037753 \cdot 4215856658533108520354659333
21 2^{33} \cdot 3^8 \cdot 83 \cdot 281 \cdot 204292081063933 \cdot 5852323051960913177671486927343120669
22 2^{36} \cdot 3^7 \cdot 5 \cdot 13 \cdot 241559 \cdot 129661160424791080992764645120871929236425763066453631
23 2^{39} \cdot 3^{10} \cdot 5407 \cdot 120427 \cdot 901145309 \cdot 3766352936022215583264814011876189449770138391
24 2^{41} \cdot 3^{11} \cdot 107 \cdot 739951 \cdot 2418119033203 \cdot 318514544213636008246871 \cdot 845851172573304061243151
25 2^{41} \cdot 3^9 \cdot 94513 \cdot 54260027 \cdot 25093654805621 \cdot 1059078880359738933703 \cdot 1130914320793991851927211947
26 2^{44} \cdot 3^{10} \cdot 7 \cdot 67933 \cdot 202543723 \cdot 2685265441 \cdot 156723690161879 \cdot 61930503417943235494756743955217132168381
27 2^{43} \cdot 3^{12} \cdot 5 \cdot 7 \cdot 53 \cdot 127320275760341262867826543621 \cdot p_{52}
28 2^{48} \cdot 3^{10} \cdot 17491 \cdot 28001 \cdot 25474005544131103985444236555403 \cdot p_{49}

Six-line Latin rectangles

Doyle's method can be adapted to also find R6,n, from which the following table was calculated.

n R6,n
6 2^6 \cdot 3 \cdot 7^2
7 2^{10} \cdot 3 \cdot 5 \cdot 1103
8 2^{11} \cdot 3 \cdot 7 \cdot 173 \cdot 45077
9 2^{14} \cdot 3^5 \cdot 3253351007
10 2^{14} \cdot 3^3 \cdot 5 \cdot 26053 \cdot 15110358097
11 2^{17} \cdot 3^2 \cdot 5 \cdot 31 \cdot 2334139 \cdot 225638611943
12 2^{17} \cdot 3^3 \cdot 5 \cdot 131 \cdot 110630813 \cdot 65475601447957
13 2^{21} \cdot 3^3 \cdot 5 \cdot 7 \cdot 43331 \cdot 51859042054524469407499

Notes

  1. ↑ http://en.wikipedia.org/wiki/Latin_square
  2. ↑ B. D. McKay, I. M. Wanless, On the number of Latin squares, Ann. Comb. 9 (2005) 335--344.
  3. ↑ N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://www.research.att.com/~njas/sequences/A002860
  4. ↑ 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.
  5. ↑ A. Cayley, On Latin squares, Messenger of Math., 19 (1890) 135--137.
  6. ↑ 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.
  7. ↑ P. A. MacMahon, Combinatory Analysis, Chelsea, 1960.
  8. ↑ B. D. McKay, A. Meynert, and W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007) 98--119.
  9. ↑ H. Minc, Permanents, Addison-Wesley, 1978. Encyclopedia of Mathematics and its Applications, volume 6.
  10. ↑ 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.
  11. ↑ J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.
  12. ↑ 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
  13. ↑ 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.
  14. ↑ N. Y. Kuznetsov, Estimating the number of Latin rectangles by the fast simulation method, Cybernet. Systems Anal., 45 (2009) 69--75.
  15. ↑ C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, Bull. Amer. Math. Soc. (N.S.) 10 (1984) 91--92.
  16. ↑ http://www.research.att.com/~njas/sequences/A000166
  17. ↑ http://www.research.att.com/~njas/sequences/A000186
  18. ↑ http://www.research.att.com/~njas/sequences/A000573
  19. ↑ 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
  20. ↑ C. J. Colbourn, J. H. Dinitz, et al., The CRC Handbook of Combinatorial Designs, CRC Press, 1996.
  21. ↑ http://en.wikipedia.org/wiki/Problems_in_Latin_squares
  22. ↑ http://en.wikipedia.org/wiki/Derangement
  23. ↑ J. Riordan, A recurrence relation for three-line Latin rectangles, Amer. Math. Monthly 59 (3) (1952) 159-162.
  24. ↑ http://code.google.com/p/latinrectangles/downloads/list
  25. ↑ http://www.alpertron.com.ar/ECM.HTM
  26. ↑ F. W. Light, Jr, A procedure for the enumeration of 4 \times n Latin rectangles, Fibonacci Quart., 11 (1973) 241-246.
  27. ↑ K. B. Athreya, C. R. Pranesachar, and N. M. Singhi, On the number of Latin rectangles and chromatic polynomial of L(Kr,s), European J. Combin., 1 (1980) 9-17.
  28. ↑ 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.
  29. ↑ I. M. Gessel, Counting Latin rectangles, Bull. Amer. Math. Soc., 16 (1987), 79-83.
  30. ↑ 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.
Retrieved from "http://combinatoricswiki.org/wiki/Enumeration_of_Latin_Squares_and_Rectangles"