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[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 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[3]. 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 [4], which we reproduce below. We omit R1,n = 1. Sloane's [5] 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[6], Cayley[7] and MacMahon[8][9]. A survey is provided by McKay, Meynert and Myrvold[10]. An upper bound on Rn are obtained through the study of permanents[11][12]. A lower bound on Rn 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 k \times n Latin rectangles was given by Goldsil and McKay[17] 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[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 Dn of derangements[24] 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[25] 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[26] 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[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 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. D. S. Stones, On the number of Latin rectangles, Ph.D. thesis, Monash University, 2010. [1]
  2. D. S. Stones, The many formulae for the number of Latin rectangles. Electron. J. Combin., 17 (2010), A1. [2]
  3. http://en.wikipedia.org/wiki/Latin_square
  4. B. D. McKay, I. M. Wanless, On the number of Latin squares, Ann. Comb. 9 (2005) 335--344.
  5. N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://www.research.att.com/~njas/sequences/A002860
  6. 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.
  7. A. Cayley, On Latin squares, Messenger of Math., 19 (1890) 135--137.
  8. 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.
  9. P. A. MacMahon, Combinatory Analysis, Chelsea, 1960.
  10. B. D. McKay, A. Meynert, and W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007) 98--119.
  11. H. Minc, Permanents, Addison-Wesley, 1978. Encyclopedia of Mathematics and its Applications, volume 6.
  12. 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.
  13. J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.
  14. 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
  15. 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.
  16. N. Y. Kuznetsov, Estimating the number of Latin rectangles by the fast simulation method, Cybernet. Systems Anal., 45 (2009) 69--75.
  17. C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, Bull. Amer. Math. Soc. (N.S.) 10 (1984) 91--92.
  18. http://www.research.att.com/~njas/sequences/A000166
  19. http://www.research.att.com/~njas/sequences/A000186
  20. http://www.research.att.com/~njas/sequences/A000573
  21. 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
  22. C. J. Colbourn, J. H. Dinitz, et al., The CRC Handbook of Combinatorial Designs, CRC Press, 1996.
  23. http://en.wikipedia.org/wiki/Problems_in_Latin_squares
  24. http://en.wikipedia.org/wiki/Derangement
  25. J. Riordan, A recurrence relation for three-line Latin rectangles, Amer. Math. Monthly 59 (3) (1952) 159-162.
  26. http://code.google.com/p/latinrectangles/downloads/list
  27. http://www.alpertron.com.ar/ECM.HTM
  28. F. W. Light, Jr, A procedure for the enumeration of 4 \times n Latin rectangles, Fibonacci Quart., 11 (1973) 241-246.
  29. 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.
  30. 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.
  31. I. M. Gessel, Counting Latin rectangles, Bull. Amer. Math. Soc., 16 (1987), 79-83.
  32. 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.