拉丁方阵

拉丁方阵（英语：Latin square）是一种 n × n 的方阵，在这种 n × n 的方阵里，恰有 n 种不同的元素，每一种不同的元素在同一行或同一列里只出现一次。以下是两个拉丁方阵举例：

一个7x7的拉丁方阵

${\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)的子集合，同型的拉丁方阵属于同一个同型类别，而不属于同一个同型类别的拉丁方阵则不同型。

拉丁方阵的正交

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

希腊拉丁方阵

根据前面所得到关于正交的定义，两个拉丁方阵相正交所得到的方阵为希腊拉丁方阵(Graeco-Latin square)。 事实上，并不是任意阶数的拉丁方都存在一对正交拉丁方，也就是说，并不是任意阶数的拉丁方均存在希腊拉丁方阵。2阶和6阶的希腊拉丁方阵不存在，其他所有阶的希腊拉丁方阵都存在。

正交拉丁方

定理

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

应用

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

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

事实上，当阶数n是质数或者质数的幂次时，必定存在n-1个正交拉丁方，另外，当n除以4余1或2，而且n不是两个平方数的和（0也算作平方数），就一定不存在n-1个正交的拉丁方，而对于10阶的情形，已经确定至少存在2个正交的拉丁方，但是不存在9个正交的拉丁方，因此10阶正交拉丁方的个数最少是2，最大是8（因为到目前为止，连3个正交的10阶拉丁方都还没找到，所以有猜测是10阶正交拉丁方的个数是2），对于12阶，已经确定至少存在5个正交的拉丁方了。

拉丁方阵的数量

目前，没有公式可以计算 n × n 的拉丁方阵的数量，当 n 很大时，拉丁方阵的数量的最精确的估计值，其上下界也相差很远。 具体估计公式为： $\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

拉丁矩阵

主条目：拉丁矩阵

若不要求行数等于列数，而考虑 $r<n$ 时 $r\times n$ 大小的矩阵，且将“$n$ 种元素各在每行每列恰好出现一次”的条件，放宽成“至多出现一次”，则得到拉丁矩阵。利用图论中有关二部图匹配的霍尔婚配定理，可以证明任意 $r\times n$ 拉丁矩阵皆可扩展成 $(r+1)\times n$ 拉丁矩阵，并可如此重复，直至得到完整的拉丁方阵。

参考文献

• 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. 
  • 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）. 
• 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
• Magic Square in Latin Square

参见

• 数独
• 吠陀方形