拉丁方陣
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Fisher-stainedglass-gonville-caius.jpg/220px-Fisher-stainedglass-gonville-caius.jpg)
拉丁方陣(英語: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 | 拉丁方陣的標準型的數量(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]
參考文獻
- ^ 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.
- ^ 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.
- ^ 正交拉丁方表. http://faculty.math.tsinghua.edu.cn/~xlu/pdf/c5-Latin-squares.pdf[失效連結]
- ^ (OEIS數列A001438)
- ^ Hall, Marshall. An existence theorem for latin squares. Bull. Amer. Math. Soc. 1945, 51: 387–388. doi:10.1090/S0002-9904-1945-08361-X.
- 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. 外部連結存在於
|publisher=
(幫助) - 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). 外部連結存在於
|publisher=
(幫助)
- 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. 外部連結存在於
- 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
參見
|
|