Enumeration of Latin Squares and Rectangles

Author's note: This is currently a snippet from my PhD thesis On the number of Latin rectangles<ref>D. S. Stones, On the number of Latin rectangles, Ph.D. thesis, Monash University, 2010. [1]</ref> and the paper The many formulae for the number of Latin rectangles<ref>D. S. Stones, The many formulae for the number of Latin rectangles. Electron. J. Combin., 17 (2010), A1. [2]</ref>. I can be contacted by email: douglas.stones (at) sci.monash.edu.au

- Douglas S. Stones

Introduction

A [math]k \times n[/math] Latin rectangle is a [math]k \times n[/math] array [math]L=(l_{ij})[/math] of [math]n[/math] symbols such that each symbol occurs exactly once in each row and at most once in each column. If [math]k=n[/math] then [math]L[/math] is called a Latin square<ref>http://en.wikipedia.org/wiki/Latin_square</ref>. A Latin rectangle on the symbols [math]\mathbb{Z}_n[/math] is called normalised if the first row is [math](0,1, \dots, n-1)[/math] and called reduced if the first row is [math](0,1, \dots, n-1)[/math] and the first column is [math](0,1, \dots ,k-1)^T[/math]. Let [math]L_{k,n}[/math] denote the number of [math]k \times n[/math] Latin rectangles, [math]K_{k,n}[/math] denote the number of [math]k \times n[/math] normalised Latin rectangles and let [math]R_{k,n}[/math] denote the number of reduced [math]k \times n[/math] Latin rectangles.. The total number of [math]k \times n[/math] Latin rectangles is [math]L_{k,n}=n! K_{k,n} = \frac{n! (n-1)!} {(n-k)!} R_{k,n}[/math]. In the case of Latin squares, the numbers [math]L_{n,n}[/math], [math]K_{n,n}[/math] and [math]R_{n,n}[/math] shall be denoted [math]L_n[/math], [math]K_n[/math] and [math]R_n[/math] respectively.

The values of [math]R_{k,n}[/math] for [math]1 \leq k \leq n \leq 11[/math] were given by McKay and Wanless <ref>B. D. McKay, I. M. Wanless, On the number of Latin squares, Ann. Comb. 9 (2005) 335--344.</ref>, which we reproduce below. We omit [math]R_{1,n}=1[/math]. Sloane's <ref>N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://www.research.att.com/~njas/sequences/A002860</ref> A002860 lists [math]K_n[/math].

	[math]n=2[/math]	[math]3[/math]	[math]4[/math]	[math]5[/math]	[math]6[/math]	[math]7[/math]	[math]8[/math]	[math]9[/math]
[math]k=2[/math]	[math]1[/math]	[math]1[/math]	[math]3[/math]	[math]11[/math]	[math]53[/math]	[math]3 \!\cdot\! 103[/math]	[math]13 \!\cdot\! 163[/math]	[math]11 \!\cdot\! 37 \!\cdot\! 41[/math]
[math]3[/math]		[math]1[/math]	[math]2^2[/math]	[math]2 \!\cdot\! 23[/math]	[math]2^3 \!\cdot\! 7 \!\cdot\! 19[/math]	[math]2^4 \!\cdot\! 2237[/math]	[math]2^6 \!\cdot\! 26153[/math]	[math]2^5 \!\cdot\! 13 \!\cdot\! 167 \!\cdot\! 1489[/math]
[math]4[/math]			[math]2^2[/math]	[math]2^3 \!\cdot\! 7[/math]	[math]2^3 \!\cdot\! 3^2 \!\cdot\! 7 \!\cdot\! 13[/math]	[math]2^5 \!\cdot\! 3 \!\cdot\! 19 \!\cdot\! 709[/math]	[math]2^6 \!\cdot\! 3 \!\cdot\! 159 \!\cdot\! 14713[/math]	[math]2^7 \!\cdot\! 3^4 \!\cdot\! 20025517[/math]
[math]5[/math]				[math]2^3 \!\cdot\! 7[/math]	[math]2^6 \!\cdot\! 3 \!\cdot\! 7^2[/math]	[math]2^8 \!\cdot\! 3 \!\cdot\! 5^2 \!\cdot\! 587[/math]	[math]2^{11} \!\cdot\! 3 \!\cdot\! 23 \!\cdot\! 192529[/math]	[math]2^{11} \!\cdot\! 3^4 \!\cdot\! 13 \!\cdot\! 52251029[/math]
[math]6[/math]					[math]2^6 \!\cdot\! 3 \!\cdot\! 7^2[/math]	[math]2^{10} \!\cdot\! 3 \!\cdot\! 5 \!\cdot\! 1103[/math]	[math]2^{11} \!\cdot\! 3 \!\cdot\! 7 \!\cdot\! 173 \!\cdot\! 45077[/math]	[math]2^{14} \!\cdot\! 3^5 \!\cdot\! 3253351007[/math]
[math]7[/math]						[math]2^{10} \!\cdot\! 3 \!\cdot\! 5 \!\cdot\! 1103[/math]	[math]2^{17} \!\cdot\! 3 \!\cdot\! 1361291[/math]	[math]2^{15} \!\cdot\! 3^2 \!\cdot\! 61 \!\cdot\! 12923 \!\cdot\! 965171[/math]
[math]8[/math]							[math]2^{17} \!\cdot\! 3 \!\cdot\! 1361291[/math]	[math]2^{21} \!\cdot\! 3^2 \!\cdot\! 5231 \!\cdot\! 3824477[/math]
[math]9[/math]								[math]2^{21} \!\cdot\! 3^2 \!\cdot\! 5231 \!\cdot\! 3824477[/math]

	[math]n=10[/math]	[math]n=11[/math]
[math]k=2[/math]	[math]3^2 \!\cdot\! 16481[/math]	[math]1468457[/math]
[math]3[/math]	[math]2^6 \!\cdot\! 23 \!\cdot\! 61 \!\cdot\! 90821[/math]	[math]2^7 \!\cdot\! 13 \!\cdot\! 23 \!\cdot\! 20851549[/math]
[math]4[/math]	[math]2^8 \!\cdot\! 3^3 \!\cdot\! 71 \!\cdot\! 271 \!\cdot\! 1106627[/math]	[math]2^{10} \!\cdot\! 3^2 \!\cdot\! 1823 \!\cdot\! 8569184461[/math]
[math]5[/math]	[math]2^{16} \!\cdot\! 3^6 \!\cdot\! 19 \!\cdot\! 97 \!\cdot\! 8483617[/math]	[math]2^{13} \!\cdot\! 3^2 \!\cdot\! 29 \!\cdot\! 168293 \!\cdot\! 20936295857[/math]
[math]6[/math]	[math]2^{14} \!\cdot\! 3^3 \!\cdot\! 5 \!\cdot\! 26053 \!\cdot\! 15110358097[/math]	[math]2^{17} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 31 \!\cdot\! 2334139 \!\cdot\! 225638611943[/math]
[math]7[/math]	[math]2^{20} \!\cdot\! 3^3 \!\cdot\! 5 \!\cdot\! 509 \!\cdot\! 2458531126109[/math]	[math]2^{21} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 9437 \!\cdot\! 269623520098467133[/math]
[math]8[/math]	[math]2^{21} \!\cdot\! 3^3 \!\cdot\! 5 \!\cdot\! 11 \!\cdot\! 13^2 \!\cdot\! 37 \!\cdot\! 1381 \!\cdot\! 159597187[/math]	[math]2^{28} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 97 \!\cdot\! 73488673152815765447[/math]
[math]9[/math]	[math]2^{28} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 31 \!\cdot\! 37 \!\cdot\! 1468457 \!\cdot\! 547135293937[/math]	[math]2^{32} \!\cdot\! 3^3 \!\cdot\! 5 \!\cdot\! 61 \!\cdot\! 7487 \!\cdot\! 260951 \!\cdot\! 42053669617[/math]
[math]10[/math]	[math]2^{28} \!\cdot\! 3^2 \!\cdot\! 5 \!\cdot\! 31 \!\cdot\! 37 \!\cdot\! 1468457 \!\cdot\! 547135293937[/math]	[math]2^{35} \!\cdot\! 3^4 \!\cdot\! 5 \!\cdot\! 2801 \!\cdot\! 2206499 \!\cdot\! 62368028479[/math]
[math]11[/math]		[math]2^{35} \!\cdot\! 3^4 \!\cdot\! 5 \!\cdot\! 2801 \!\cdot\! 2206499 \!\cdot\! 62368028479[/math]

The enumeration of [math]R_n[/math] has a history stretching back to Euler<ref>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.</ref>, Cayley<ref>A. Cayley, On Latin squares, Messenger of Math., 19 (1890) 135--137.</ref> and MacMahon<ref>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.</ref><ref>P. A. MacMahon, Combinatory Analysis, Chelsea, 1960.</ref>. A survey is provided by McKay, Meynert and Myrvold<ref>B. D. McKay, A. Meynert, and W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007) 98--119.</ref>. An upper bound on [math]R_n[/math] are obtained through the study of permanents<ref>H. Minc, Permanents, Addison-Wesley, 1978. Encyclopedia of Mathematics and its Applications, volume 6.</ref><ref>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.</ref>. A lower bound on [math]R_n[/math] is given by van Lint and Wilson<ref>J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.</ref>. Estimates for the number of Latin squares were given by McKay and Rogoyski<ref>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</ref>, Zhang and Ma<ref>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.</ref> and Kuznetsov<ref>N. Y. Kuznetsov, Estimating the number of Latin rectangles by the fast simulation method, Cybernet. Systems Anal., 45 (2009) 69--75.</ref>.

A survey of the enumeration of Latin rectangles was given by Stones and Wanless. An asymptotic formula for the number of [math]k \times n[/math] Latin rectangles was given by Goldsil and McKay<ref>C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, Bull. Amer. Math. Soc. (N.S.) 10 (1984) 91--92.</ref> as [math]n \rightarrow \infty[/math] with [math]k=o(n^{6/7})[/math]. The value of [math]K_{2,n}[/math], [math]K_{3,n}[/math] and [math]K_{4,n}[/math] is given by Sloane's A000166<ref>http://www.research.att.com/~njas/sequences/A000166</ref>, A000186<ref>http://www.research.att.com/~njas/sequences/A000186</ref> and A000573<ref>http://www.research.att.com/~njas/sequences/A000573</ref>, respectively.

Bailey and Cameron<ref>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</ref> (see also the CRC Handbook<ref>C. J. Colbourn, J. H. Dinitz, et al., The CRC Handbook of Combinatorial Designs, CRC Press, 1996.</ref>) discuss combinatorial objects equivalent to Latin squares. Wikipedia host a list of problems in the theory of Latin squares<ref>http://en.wikipedia.org/wiki/Problems_in_Latin_squares</ref>.

The number [math]D_n[/math] of derangements<ref>http://en.wikipedia.org/wiki/Derangement</ref> is related to the number of [math]2 \times n[/math] Latin rectangles by

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

Riordan<ref>J. Riordan, A recurrence relation for three-line Latin rectangles, Amer. Math. Monthly 59 (3) (1952) 159-162.</ref> gave the credit to Yamamoto for the equation

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

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

Four-line Latin rectangles

A formula for the number of reduced [math]4 \times n[/math] Latin rectangles is given by Doyle, from which the following table of values of [math]R_{4,n}[/math] was calculated. The c code used has been uploaded to Google Code<ref>http://code.google.com/p/latinrectangles/downloads/list</ref> along with code for [math]R_{5,n}[/math] and [math]R_{6,n}[/math]. We use [math]p_m[/math] to denote an [math]m[/math]-digit prime number and [math]c_m[/math] to denote an [math]m[/math]-digit composite number. Factorisations were performed using Dario Alpern's applet<ref>http://www.alpertron.com.ar/ECM.HTM</ref>. Other formulae for the number of four-line Latin rectangles are given by Light Jr.<ref>F. W. Light, Jr, A procedure for the enumeration of [math]4 \times n[/math] Latin rectangles, Fibonacci Quart., 11 (1973) 241-246.</ref>, Athreya, Pranesachar and Singhi<ref>K. B. Athreya, C. R. Pranesachar, and N. M. Singhi, On the number of Latin rectangles and chromatic polynomial of [math]L(K_{r,s})[/math], European J. Combin., 1 (1980) 9-17.</ref> (see also Pranesachar<ref>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.</ref>) and Gessel<ref>I. M. Gessel, Counting Latin rectangles, Bull. Amer. Math. Soc., 16 (1987), 79-83.</ref>. A similar claim is made by de Gennaro<ref>A. de Gennaro, How many Latin rectangles are there?, (2007). arXiv:0711.0527v1 [math.CO], 20 pp. http://arxiv.org/abs/0711.0527</ref>.

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

Five-line Latin rectangles

Doyle's method can be adapted to also find [math]R_{5,n}[/math], from which the following table was calculated.

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

Six-line Latin rectangles

Doyle's method can be adapted to also find [math]R_{6,n}[/math], from which the following table was calculated.

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

Notes

<references />

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.