跳至內容

拉丁方陣

維基百科,自由的百科全書
一個7x7的拉丁方陣

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

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

拉丁方陣的標準型

[編輯]

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

同型類別

[編輯]

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

拉丁方陣的正交

[編輯]

設有兩個階數相同的拉丁方陣,其中將所有放置位置相同的元素組成一個二元組,組合成一個新的矩陣。 當這個新的矩陣中每一個元素互不相同時,拉丁方陣是互相正交的。 此時,即為一對正交拉丁方。 而在階數固定的情況下,所有兩兩正交的拉丁方所成的集合稱為正交拉丁方族

希臘拉丁方陣

[編輯]

根據前面所得到關於正交的定義,兩個拉丁方陣相正交所得到的方陣為希臘拉丁方陣(Graeco-Latin square)。 事實上,並不是任意階數的拉丁方都存在一對正交拉丁方,也就是說,並不是任意階數的拉丁方均存在希臘拉丁方陣。2階和6階的希臘拉丁方陣不存在,其他所有階的希臘拉丁方陣都存在。

正交拉丁方

[編輯]

定理

[編輯]

若n階拉丁方存在r個兩兩正交的拉丁方,那麼

應用

[編輯]

當該定理中的等號成立時,該階正交拉丁方族稱為完全的。 可以分析得到,當n為0或1時,存在無限多個正交的拉丁方,當n為2時,不存在正交拉丁方族。 此外,當n為6時,也不存在正交拉丁方族,這個結論是通過對三十六軍官問題的嘗試得到的。 三十六軍官問題指的是是否有一個解決方案使得來自6個不同地區的6個不同軍階的軍官排成的方陣,其中每一行每一列的軍官都來自於不同的地區且具有不同的軍階。 而該問題的方案即為6階正交拉丁方的個數,該問題於1901年被Gaston Tarry證明為無解[1][2]。 除了上述三種情況外,當階數小於等於8時,均存在有n-1個正交的拉丁方。

如當n=3時,存在兩個正交的拉丁方。 當階數更多時,可以通過正交拉丁方表[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 很大時,拉丁方陣的數量的最精確的估計值,其上下界也相差很遠。 具體估計公式為:

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

拉丁矩陣

[編輯]

若不要求行數等於列數,而考慮 大小的矩陣,且將「 種元素各在每行每列恰好出現一次」的條件,放寬成「至多出現一次」,則得到拉丁矩陣。利用圖論中有關二部圖匹配霍爾婚配定理,可以證明任意 拉丁矩陣皆可擴展成 拉丁矩陣,並可如此重複,直至得到完整的拉丁方陣[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. 

外部連結

[編輯]

參見

[編輯]