拉丁方陣

维基百科,自由的百科全书
跳转至: 导航搜索
一個7x7的拉丁方陣

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

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

拉丁方陣的標準型[编辑]

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

同型類別[编辑]

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

拉丁方阵的正交[编辑]

设有两个阶数相同(为)的拉丁方阵,其中将所有放置位置相同的元素组合成一个元组,组合成一个新的矩阵。 当这个新的矩阵中每一个元素互不相同时,拉丁方阵是互相正交的。 此时,即为一对正交拉丁方。 而在阶数固定的情况下,所有两两正交的拉丁方所成的集合称为正交拉丁方族

希臘拉丁方陣[编辑]

根据前面所得到关于正交的定义,兩個拉丁方陣相正交所得到的方陣為希臘拉丁方陣(Graeco-Latin square)。 事实上,并不是任意阶数的拉丁方都存在一对正交拉丁方,也就是说,并不是任意阶数的拉丁方均存在希臘拉丁方陣

正交拉丁方[编辑]

定理[编辑]

若n阶拉丁方存在r个两两正交的拉丁方,那么

应用[编辑]

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

如当n=3时,存在两个正交的拉丁方。 当阶数更多时,可以通过正交拉丁方表[3]得到正交拉丁方族。

拉丁方陣的數量[编辑]

目前,沒有公式可以計算 n × n 的拉丁方陣的數量,而当前最精确的公式在當 n 很大時,拉丁方陣的數量的最精確的估計值,其上下界也相差很遠。 具体估计公式为:

以下是已知的數值。當 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

參考文獻[编辑]

  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

外部連結[编辑]

參見[编辑]