拉丁方陣（）是一種 n × n 的方陣，在這種 n × n 的方陣裡，恰有 n 種不同的元素，每一種不同的元素在同一行或同一列裡只出現一次。以下是兩個拉丁方陣舉例：
\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^{(1)}_{i,j})_{n \times n}, A_2=(a^{(2)}_{i,j})_{n \times n}，其中将所有放置位置相同的元素组成一个二元组，组合成一个新的矩阵((a^{(1)}_{i,j},a^{(2)}_{i,j}))_{n \times n}。
当这个新的矩阵((a^{(1)}_{i,j},a^{(2)}_{i,j}))_{n \times n}中每一个元素互不相同时，拉丁方阵A_1和A_2是互相正交的。
此时，A_1和A_2即为一对正交拉丁方。
而在阶数固定的情况下，所有两两正交的拉丁方所成的集合称为正交拉丁方族。
希臘拉丁方陣
根据前面所得到关于正交的定义，兩個拉丁方陣相正交所得到的方陣為希臘拉丁方陣(Graeco-Latin square)。
事实上，并不是任意阶数的拉丁方都存在一对正交拉丁方，也就是说，并不是任意阶数的拉丁方均存在希臘拉丁方陣。2阶和6阶的希腊拉丁方阵不存在，其他所有阶的希腊拉丁方阵都存在。
正交拉丁方
定理
若n阶拉丁方存在r个两两正交的拉丁方，那么r \le 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 \le 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}\ge L_n \ge \frac{(n!)^{2n}}{n^{n^2}}
以下是已知的數值。當 n 增加時，拉丁方陣的數量急速增多。
拉丁矩陣
若不要求行數等於列數，而考慮 r 時 r \times n 大小的矩陣，且將「n 種元素各在每行每列恰好出現一次」的條件，放寬成「至多出現一次」，則得到拉丁矩陣。利用圖論中有關二部圖匹配的霍爾婚配定理，可以證明任意 r \times n 拉丁矩陣皆可擴展成 (r+1) \times n 拉丁矩陣，並可如此重複，直至得到完整的拉丁方陣。
參考文獻
- Pre-publication chapters are available on-line.
*
*
*
**
**
*
*
*
*
*
*
- J. H. van Lint, R. M. Wilson: A Course in Combinatorics. Cambridge University Press 1992,ISBN 978-0-521-42260-4, p. 157
外部連結
*
- [http://www.math.nctu.edu.tw/hlfu/getCourseFile.php?CID=48&type=download] Combinatorial Designs
- [http://eom.springer.de/L/l057620.htm Latin Squares] in the Encyclopaedia of Mathematics
- [http://www.cut-the-knot.org/Curriculum/Algebra/Latin.shtml Latin Squares in Java] at cut-the-knot
- [http://www.cut-the-knot.org/Curriculum/Combinatorics/InfiniteLatinSquare.shtml Infinite Latin Square (Java)] at cut-the-knot
- [https://web.archive.org/web/20131224123214/http://www.muljadi.org/MagicSudoku.htm Magic Square in Latin Square]
參見
*數獨
*吠陀方形
评论 (0)