拉丁方陣

拉丁方陣（英語：Latin square）是一種 n × n 的方陣，在這種 n × n 的方陣裡，恰有 n 種不同的元素，每一種不同的元素在同一行或同一列裡只出現一次。以下是兩個拉丁方陣舉例：

一個7x7的拉丁方陣

${\displaystyle {\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}{\begin{bmatrix}a&b&d&c\\b&c&a&d\\c&d&b&a\\d&a&c&b\end{bmatrix}}}$

拉丁方陣有此名稱是因為瑞士數學家和物理學家欧拉使用拉丁字母來做為拉丁方陣裡的元素的符號。

拉丁方陣的標準型

當一個拉丁方陣的第一行與第一列的元素按順序排列時，称為這個拉丁方陣的標準型，英語稱為"reduced Latin square, normalized Latin square, 或Latin square in standard form"。

同型類別

参见：等价类和集合划分

許多對於拉丁方陣的運算都會產生新的拉丁方陣。例如說，交換拉丁方陣裡的行、交換拉丁方陣裡的列、或是交換拉丁方陣裡的元素的符號，都會得到一個新的拉丁方陣。交換拉丁方陣裡的行、交換拉丁方陣裡的列、或是交換拉丁方陣裡的元素的符號所得的新的拉丁方陣與原來的拉丁方陣稱為同型(isotopic)。同型(isotopism)是一個等價關係，因此所有的拉丁方陣所成的集合可以分成同型類別(isotopic class)的子集合，同型的拉丁方陣屬於同一個同型類別，而不屬於同一個同型類別的拉丁方陣則不同型。

拉丁方阵的正交

设有两个阶数相同的拉丁方阵${\displaystyle A_{1}=(a_{i,j}^{(1)})_{n\times n},A_{2}=(a_{i,j}^{(2)})_{n\times n}}$ ，其中将所有放置位置相同的元素组成一个二元组，组合成一个新的矩阵${\displaystyle ((a_{i,j}^{(1)},a_{i,j}^{(2)}))_{n\times n}}$ 。 当这个新的矩阵${\displaystyle ((a_{i,j}^{(1)},a_{i,j}^{(2)}))_{n\times n}}$ 中每一个元素互不相同时，拉丁方阵${\displaystyle A_{1}}$ 和${\displaystyle A_{2}}$ 是互相正交的。 此时，${\displaystyle A_{1}}$ 和${\displaystyle A_{2}}$ 即为一对正交拉丁方。 而在阶数固定的情况下，所有两两正交的拉丁方所成的集合称为正交拉丁方族。

希臘拉丁方陣

根据前面所得到关于正交的定义，兩個拉丁方陣相正交所得到的方陣為希臘拉丁方陣(Graeco-Latin square)。 事实上，并不是任意阶数的拉丁方都存在一对正交拉丁方，也就是说，并不是任意阶数的拉丁方均存在希臘拉丁方陣，n階希臘拉丁方陣存在的充要條件是n+2不是2的冪，所以其實幾乎所有的階數都存在希臘拉丁方陣。

正交拉丁方

定理

若n阶拉丁方存在r个两两正交的拉丁方，那么${\displaystyle r\leq n-1}$ 。

应用

当该定理中的等号成立时，该阶正交拉丁方族称为完全的。 可以分析得到，当n为0或1时，存在无限多个正交的拉丁方，当n为2时，不存在正交拉丁方族。 此外，当n为6时，也不存在正交拉丁方族，这个结论是通过对三十六军官问题的尝试得到的。 三十六军官问题指的是是否有一个解决方案使得来自6个不同地区的6个不同军衔的军官排成${\displaystyle 6\times 6}$ 的方阵，其中每一行每一列的军官都来自于不同的地区且具有不同的军衔。 而该问题的方案即为6阶正交拉丁方的个数，该问题于1901年被Gaston Tarry证明为无解^[1][2]。 除了上述三种情况外，当阶数小于等于8时，均存在有n-1个正交的拉丁方。

如当n=3时，存在两个正交的拉丁方。 ${\displaystyle {\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}}$  ${\displaystyle {\begin{bmatrix}1&2&3\\3&1&2\\2&3&1\\\end{bmatrix}}}$  当阶数更多时${\displaystyle n\leq 8}$ ，可以通过正交拉丁方表^[3]得到正交拉丁方族。

事實上，當階數n是質數或者質數的冪次時，必定存在n-1個正交拉丁方，另外，當n除以4餘1或2，而且n不是兩個平方數的和（0也算作平方數），就一定不存在n-1個正交的拉丁方，而對於10階的情形，已經確定至少存在2個正交的拉丁方，但是不存在9個正交的拉丁方，因此10階正交拉丁方的個數最少是2，最大是8（因為到目前為止，連3個正交的10階拉丁方都還沒找到，所以有猜測是10階正交拉丁方的個數是2），對於12階，已經確定至少存在5個正交的拉丁方了^[4]。

拉丁方陣的數量

目前，沒有公式可以計算 n × n 的拉丁方陣的數量，當 n 很大時，拉丁方陣的數量的最精確的估計值，其上下界也相差很遠。 具体估计公式为： ${\displaystyle \prod _{k=1}^{n}(k!)^{n/k}\geq L_{n}\geq {\frac {(n!)^{2n}}{n^{n^{2}}}}}$ 

以下是已知的數值。當 n 增加時，拉丁方陣的數量急速增多。

不同大小的 n × n 的拉丁方陣的數量

n	拉丁方陣的標準型的數量（OEIS數列A000315）	所有拉丁方陣的數量（OEIS數列A002860）
1	1	1
2	1	2
3	1	12
4	4	576
5	56	161280
6	9408	812851200
7	16942080	61479419904000
8	535281401856	108776032459082956800
9	377597570964258816	5524751496156892842531225600
10	7580721483160132811489280	9982437658213039871725064756920320000
11	5363937773277371298119673540771840	776966836171770144107444346734230682311065600000

拉丁矩陣

主条目：拉丁矩陣（英语：Latin rectangle）

若不要求行數等於列數，而考慮 ${\displaystyle r<n}$  時 ${\displaystyle r\times n}$  大小的矩陣，且將「${\displaystyle n}$  種元素各在每行每列恰好出現一次」的條件，放寬成「至多出現一次」，則得到拉丁矩陣。利用圖論中有關二部圖匹配的霍爾婚配定理，可以證明任意 ${\displaystyle r\times n}$  拉丁矩陣皆可擴展成 ${\displaystyle (r+1)\times n}$  拉丁矩陣，並可如此重複，直至得到完整的拉丁方陣。^[5]

參考文獻

1. Tarry, Gaston. Le Probléme de 36 Officiers. Compte Rendu de l'Association Française pour l'Avancement de Science Naturel (Secrétariat de l'Association). 1900, 1: 122–123. 
2. Tarry, Gaston. Le Probléme de 36 Officiers. Compte Rendu de l'Association Française pour l'Avancement de Science Naturel (Secrétariat de l'Association). 1901, 2: 170–203. 
3. 正交拉丁方表. http://faculty.math.tsinghua.edu.cn/~xlu/pdf/c5-Latin-squares.pdf
4. （OEIS數列A001438）
5. Hall, Marshall. An existence theorem for latin squares. Bull. Amer. Math. Soc. 1945, 51: 387–388. doi:10.1090/S0002-9904-1945-08361-X. 

• Bailey, R.A. 6 Row-Column designs and 9 More about Latin squares. Design of Comparative Experiments. Cambridge University Press. 2008 [2013-12-22]. ISBN 978-0-521-68357-9. MR 2422352. （原始内容于2013-12-24）.  Pre-publication chapters are available on-line.
• Dénes, J.; Keedwell, A. D. Latin squares and their applications. New York-London: Academic Press. 1974: 547. ISBN 0-12-209350-X. MR 0351850. 
• Dénes, J. H.; Keedwell, A. D. Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics 46. Paul Erdős (foreword). Amsterdam: Academic Press. 1991: xiv+454. ISBN 0-444-88899-3. MR 1096296. With contributions by G. B. Belyavskaya, A. E. Brouwer, T. Evans, K. Heinrich, C. C. Lindner and D. A. Preece. 
• Hinkelmann, Klaus; Kempthorne, Oscar. Design and Analysis of Experiments I , II Second. Wiley. 2008. ISBN 978-0-470-38551-7. MR 2363107. 
  • Hinkelmann, Klaus; Kempthorne, Oscar. Design and Analysis of Experiments, Volume I: Introduction to Experimental Design Second. Wiley. 2008. ISBN 978-0-471-72756-9. MR 2363107.  外部链接存在于|publisher= (帮助)
  • Hinkelmann, Klaus; Kempthorne, Oscar. Design and Analysis of Experiments, Volume 2: Advanced Experimental Design First. Wiley. 2005 [2013-12-22]. ISBN 978-0-471-55177-5. MR 2129060. （原始内容于2020-08-06）.  外部链接存在于|publisher= (帮助)
• Knuth, Donald. Volume 4A: Combinatorial Algorithms, Part 1. The Art of Computer Programming First. Reading, Massachusetts: Addison-Wesley. 2011: xv+883pp. ISBN 0-201-03804-8. 
• Laywine, Charles F.; Mullen, Gary L. Discrete mathematics using Latin squares. Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: John Wiley & Sons, Inc. 1998: xviii+305. ISBN 0-471-24064-8. MR 1644242. 
• Shah, Kirti R.; Sinha, Bikas K. 4 Row-Column Designs. Theory of Optimal Designs. Lecture Notes in Statistics 54. Springer-Verlag. 1989: 66–84. ISBN 0-387-96991-8. MR 1016151. 
• Shah, K. R.; Sinha, Bikas K. Row-column designs. S. Ghosh and C. R. Rao (编). Design and analysis of experiments. Handbook of Statistics 13. Amsterdam: North-Holland Publishing Co. 1996: 903–937. ISBN 0-444-82061-2. MR 1492586. 
• Raghavarao, Damaraju. Constructions and Combinatorial Problems in Design of Experiments corrected reprint of the 1971 Wiley. New York: Dover. 1988. ISBN 0-486-65685-3. MR 1102899. 
• Street, Anne Penfold and Street, Deborah J. Combinatorics of Experimental Design. New York: Oxford University Press. 1987: 400+xiv pp. ISBN 0-19-853255-5. MR 0908490. ISBN13 0-19-853256-3. 
• J. H. van Lint, R. M. Wilson: A Course in Combinatorics. Cambridge University Press 1992,ISBN 978-0-521-42260-4, p. 157

外部連結

• 埃里克·韦斯坦因. Latin Square. MathWorld. 
• [1] （页面存档备份，存于互联网档案馆） Combinatorial Designs
• Latin Squares （页面存档备份，存于互联网档案馆） in the Encyclopaedia of Mathematics
• Latin Squares in Java （页面存档备份，存于互联网档案馆） at cut-the-knot
• Infinite Latin Square (Java) （页面存档备份，存于互联网档案馆） at cut-the-knot

參見

• 數獨
• 吠陀方形