拉丁方陣

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

一個7x7的拉丁方陣

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

拉丁方陣的標準型

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

同型類別

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

拉丁方阵的正交

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

希臘拉丁方陣

根据前面所得到关于正交的定义,兩個拉丁方陣相正交所得到的方陣為希臘拉丁方陣(Graeco-Latin square)。 事实上,并不是任意阶数的拉丁方都存在一对正交拉丁方,也就是说,并不是任意阶数的拉丁方均存在希臘拉丁方陣,n階希臘拉丁方陣存在的充要條件是n+2不是2的冪,所以其實幾乎所有的階數都存在希臘拉丁方陣。

正交拉丁方

定理

若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
111
212
3112
44576
556161280
69408812851200
71694208061479419904000
8535281401856108776032459082956800
93775975709642588165524751496156892842531225600
1075807214831601328114892809982437658213039871725064756920320000
115363937773277371298119673540771840776966836171770144107444346734230682311065600000

參考文獻

  1. Tarry, Gaston. . 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. . 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
  • Bailey, R.A. . . Cambridge University Press. 2008. ISBN 978-0-521-68357-9. MR 2422352. Pre-publication chapters are available on-line.
  • Dénes, J.; Keedwell, A. D. . New York-London: Academic Press. 1974: 547. ISBN 0-12-209350-X. MR 351850.
  • Dénes, J. H.; Keedwell, A. D. . 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. I , II Second. Wiley. 2008. ISBN 978-0-470-38551-7. MR 2363107.
    • Hinkelmann, Klaus; Kempthorne, Oscar. Second. Wiley. 2008. ISBN 978-0-471-72756-9. MR 2363107. 外部链接存在于|publisher= (帮助)
    • Hinkelmann, Klaus; Kempthorne, Oscar. First. Wiley. 2005. ISBN 978-0-471-55177-5. MR 2129060. 外部链接存在于|publisher= (帮助)
  • Knuth, Donald. . The Art of Computer Programming First. Reading, Massachusetts: Addison-Wesley. 2011: xv+883pp. ISBN 0-201-03804-8.
  • Laywine, Charles F.; Mullen, Gary L. . 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. . . Lecture Notes in Statistics 54. Springer-Verlag. 1989: 66–84. ISBN 0-387-96991-8. MR 1016151.
  • Shah, K. R.; Sinha, Bikas K. . S. Ghosh and C. R. Rao (编). . Handbook of Statistics 13. Amsterdam: North-Holland Publishing Co. 1996: 903–937. ISBN 0-444-82061-2. MR 1492586.
  • Raghavarao, Damaraju. corrected reprint of the 1971 Wiley. New York: Dover. 1988. ISBN 0-486-65685-3. MR 1102899.
  • Street, Anne Penfold and Street, Deborah J. . New York: Oxford University Press. 1987: 400+xiv pp. ISBN 0-19-853255-5. MR 908490. 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

外部連結

參見

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.