拉丁方阵

拉丁方阵英语:)是一种 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

拉丁矩阵

若不要求行数等于列数,而考虑 大小的矩阵,且将「 种元素各在每行每列恰好出现一次」的条件,放宽成「至多出现一次」,则得到拉丁矩阵。利用图论中有关二部图匹配霍尔婚配定理,可以证明任意 拉丁矩阵皆可扩展成 拉丁矩阵,并可如此重复,直至得到完整的拉丁方阵[5]

参考文献

  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%5B%5D
  4. OEIS数列A001438
  5. Hall, Marshall. . Bull. Amer. Math. Soc. 1945, 51: 387–388. doi:10.1090/S0002-9904-1945-08361-X.
  • Bailey, R.A. . . 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. . New York-London: Academic Press. 1974: 547. ISBN 0-12-209350-X. MR 0351850.
  • 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 [2013-12-22]. ISBN 978-0-471-55177-5. MR 2129060. (原始内容存档于2020-08-06). 外部链接存在于|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 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

外部链接

参见

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