拉丁方阵

拉丁方阵（英语：Latin square）是一种 n × n 的方阵，在这种 n × n 的方阵里，恰有 n 种不同的元素，每一种不同的元素在同一行或同一列里只出现一次。以下是两个拉丁方阵举例：拉丁方阵有此名称是因为瑞士数学家和物理学家欧拉使用拉丁字母来做为拉丁方阵里的元素的符号。当一个拉丁方阵的第一行与第一列的元素按顺序排列时，此为这个拉丁方阵的标准型，英语称为"reduced Latin square, normalized Latin square, 或Latin square in standard form"。许多对于拉丁方阵的运算都会产生新的拉丁方阵。例如说，交换拉丁方阵里的行、交换拉丁方阵里的列、或是交换拉丁方阵里的元素的符号，都会得到一个新的拉丁方阵。交换拉丁方阵里的行、交换拉丁方阵里的列、或是交换拉丁方阵里的元素的符号所得的新的拉丁方阵与原来的拉丁方阵称为同型(isotopic)。同型(isotopism)是一个等价关系，因此所有的拉丁方阵所成的集合可以分成同型类别(isotopic class)的子集合，同型的拉丁方阵属于同一个同型类别，而不属于同一个同型类别的拉丁方阵则不同型。设有两个阶数相同(为)的拉丁方阵 A 1 = ( a i , j ( 1 ) ) n × n , A 2 = ( a i , j ( 2 ) ) n × n {displaystyle A_{1}=(a_{i,j}^{(1)})_{ntimes n},A_{2}=(a_{i,j}^{(2)})_{ntimes n}} ，其中将所有放置位置相同的元素组合成一个元组，组合成一个新的矩阵 ( ( a i , j ( 1 ) , a i , j ( 2 ) ) ) n × n {displaystyle ((a_{i,j}^{(1)},a_{i,j}^{(2)}))_{ntimes n}} 。 当这个新的矩阵 ( ( a i , j ( 1 ) , a i , j ( 2 ) ) ) n × n {displaystyle ((a_{i,j}^{(1)},a_{i,j}^{(2)}))_{ntimes n}} 中每一个元素互不相同时，拉丁方阵 A 1 {displaystyle A_{1}} 和 A 2 {displaystyle A_{2}} 是互相正交的。 此时， A 1 {displaystyle A_{1}} 和 A 2 {displaystyle A_{2}} 即为一对正交拉丁方。 而在阶数固定的情况下，所有两两正交的拉丁方所成的集合称为正交拉丁方族。根据前面所得到关于正交的定义，两个拉丁方阵相正交所得到的方阵为希腊拉丁方阵(Graeco-Latin square)。 事实上，并不是任意阶数的拉丁方都存在一对正交拉丁方，也就是说，并不是任意阶数的拉丁方均存在希腊拉丁方阵，n阶希腊拉丁方阵存在的充要条件是n+2不是2的幂，所以其实几乎所有的阶数都存在希腊拉丁方阵。若n阶拉丁方存在r个两两正交的拉丁方，那么 r ≤ n − 1 {displaystyle rleq n-1} 。当该定理中的等号成立时，则该阶正交拉丁方族被称为完全的。 可以分析得到，当n为0或1时，存在无限多个正交的拉丁方，当n为2时，不存在正交拉丁方族。 此外，当n为6时，也不存在正交拉丁方族，这个结论是通过对三十六军官问题的尝试得到的。 三十六军官问题指的是是否有一个解决方案使得来自6个不同地区的6个不同军衔的军官排成 6 × 6 {displaystyle 6times 6} 的方阵，其中每一行每一列的军官都来自于不同的地区且具有不同的军衔。 而该问题的方案即为6阶正交拉丁方的个数，该问题于1901年被Gaston Tarry证明为无解。 除了上述三种情况外，当阶数小于等于8时，均存在有n-1个正交的拉丁方。如当n=3时，存在两个正交的拉丁方。 [ 1 2 3 2 3 1 3 1 2 ] {displaystyle {begin{bmatrix}1&2&3\2&3&1\3&1&2\end{bmatrix}}} [ 1 2 3 3 1 2 2 3 1 ] {displaystyle {begin{bmatrix}1&2&3\3&1&2\2&3&1\end{bmatrix}}} 当阶数更多时 n ≤ 8 {displaystyle nleq 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 很大时，拉丁方阵的数量的最精确的估计值，其上下界也相差很远。 具体估计公式为： ∏ k = 1 n ( k ! ) n / k ≥ L n ≥ ( n ! ) 2 n n n 2 {displaystyle prod _{k=1}^{n}(k!)^{n/k}geq L_{n}geq {frac {(n!)^{2n}}{n^{n^{2}}}}}以下是已知的数值。当 n 增加时，拉丁方阵的数量急速增多。