CW>Douglas.Stones: Reference updates

2010-07-02T04:54:41Z

Reference updates

New page

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. [http://arrow.monash.edu.au/hdl/1959.1/167114]</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. [http://www.combinatorics.org/Volume_17/Abstracts/v17i1a1.html]</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>.

<center>
{| class="wikitable" border="1"
|-
! || <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>
|}

{| class="wikitable" border="1"
|-
! || <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>
|-
|}
</center>

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
<center><math>D_n = n! \sum_{i=0}^n \frac{(-1)^i}{i!} = K_{2,n} = (n-1) R_{2,n} .</math></center>
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
<center><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></center>

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<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>.

<center>
{| class="wikitable" border="1"
! <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>
|}
</center>

==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.

<center>
{| class="wikitable" border="1"
! <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>
|}
</center>

==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.

<center>
{| class="wikitable" border="1"
! <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>
|}
</center>

==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.

[[Category:Enumeration of Latin Squares and Rectangles]]

Enumeration of Latin Squares and Rectangles - Revision history

Grahame: 1 revision imported

CW>Douglas.Stones: Reference updates

← Older revision	Revision as of 14:39, 3 January 2019
(No difference)