主题
Search

拉丁方阵

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

一个 n×n 拉丁方阵是一个 拉丁矩形，其中 k=n。具体而言，一个拉丁方阵由 n 组数字 1 到 n 排列而成，使得任何正交（行或列）都不包含相同的数字两次。例如，两个 2 阶拉丁方阵由下式给出

[1 2; 2 1],[2 1; 1 2],
(1)

三个 3 阶拉丁方阵由下式给出

[1 2 3; 2 3 1; 3 1 2],[1 2 3; 3 1 2; 2 3 1],[1 3 2; 2 1 3; 3 2 1],[1 3 2; 3 2 1; 2 1 3], [2 1 3; 1 3 2; 3 2 1],[2 1 3; 3 2 1; 1 3 2],[2 3 1; 1 2 3; 3 1 2],[2 3 1; 3 1 2; 1 2 3], [3 2 1; 1 3 2; 2 1 3],[3 2 1; 2 1 3; 1 3 2],[3 1 2; 1 2 3; 2 3 1],[3 1 2; 2 3 1; 1 2 3],
(2)

以及两个 4 阶拉丁方阵（共 576 个）由下式给出

[1 2 3 4; 2 1 4 3; 3 4 1 2; 4 3 2 1] and [1 2 3 4; 3 4 1 2; 4 3 2 1; 2 1 4 3].
(3)
LatinSquareGraphs

拉丁方阵对应于 n×n 车图的最小顶点着色，上面为 n=2 和 3 进行了说明。

阶数为 N(n,n) 的拉丁方阵的数量 n=1, 2, ... 分别为 1, 2, 12, 576, 161280, ... (OEIS A002860)。同位素不同的阶数为 L(n,n) 的拉丁方阵的数量 n=1, 2, ... 分别为 1, 1, 1, 2, 2, 22, 564, 1676267, ... (OEIS A040082)。

如果由两个数组并排放置形成的 n^2 对都不同，则称一对拉丁方阵是正交的。例如，两个拉丁方阵

[3 2 1; 2 1 3; 1 3 2] [2 3 1; 1 2 3; 3 1 2]
(4)

是正交的。阶数为 n=1, 2, ... 的正交拉丁方阵对的数量为 0, 0, 36, 3456, ... (OEIS A072377)。

第一行由 n 给出的拉丁方阵的数量 {1,2,...,n} 与对角线固定的 n 阶拉丁方阵的数量相同（即，主对角线上所有元素均为 1 的 n 阶拉丁方阵的数量）。对于 n=1, 2, ..., 这样的矩阵的数量为 1, 1, 2, 24, 1344, 1128960, ... (OEIS A000479)，并且 n 阶拉丁方阵的总数等于该数字乘以 n!。

归一化或简化的拉丁方阵是第一行和第一列由 {1,2,...,n} 给出的拉丁方阵。Nechvatal (1981)、Gessel (1987) 以及 Shao 和 Wei (1992) 给出了归一化 n×n 拉丁方阵 L(n,n) 数量的通用公式，但 L(n,n) 的渐近值尚不清楚 (MacKay 和 Wanless 2005)。N(n,n) 阶数为 n 的拉丁方阵的总数可以从下式计算得出

N(n,n)=n!(n-1)!L(n,n).
(5)

下表总结了阶数为 n=1, 2, ... 的归一化拉丁方阵的数量 (OEIS A000315)。

nL(n,n)参考文献
11
21
31
44
556Euler (1782), Cayley (1890), MacMahon (1915; 错误值)
69408Frolov (1890) 和 Tarry (1900)
716942080Frolov (1890; 错误), Norton (1939; 不完整), Sade (1948), Saxena (1951)
8535281401856Wells (1967)
9377597570964258816Bammel 和 Rothstein (1975)
107580721483160132811489280McKay 和 Rogoyski (1995)
115363937773277371298119673540771840McKay 和 Wanless (2005)
121.62×10^(44)McKay 和 Rogoyski (1995)
132.51×10^(56)McKay 和 Rogoyski (1995)
142.33×10^(70)McKay 和 Rogoyski (1995)
151.5×10^(86)McKay 和 Rogoyski (1995)

数独是拉丁方阵的一个特例。

参见

36 军官问题, Alon-Tarsi 猜想, 欧拉方阵, Kirkman 三元组系统, Lam 问题, 部分拉丁方阵, 拟群, 车图, SOMA, 数独

使用 Wolfram|Alpha 探索

参考文献

Bammel, S. E. 和 Rothstein, J. "The Number of 9×9 Latin Squares." Disc. Math. 11, 93-95, 1975.Cayley, A. "On Latin Squares." Oxford Cambridge Dublin Messenger Math. 19, 135-137, 1890.Colbourn, C. J. 和 Dinitz, J. H. (Eds.). CRC 组合设计手册。 Boca Raton, FL: CRC Press, 1996.Comtet, L. 高级组合学：有限与无限展开的艺术，修订和扩充版。 Dordrecht, Netherlands: Reidel, p. 183, 1974.Euler, L. "Recherches sur une nouvelle esp ece de quarrès magiques." Verh. Zeeuwsch Gennot. Weten Vliss 9, 85-239, 1782.Frolov, M. "Sur les permutations carrés." J. de Math. spéc. 4, 8-11 和 25-30, 1890.Gessel, I. "Counting Latin Rectangles." Bull. Amer. Math. Soc. 16, 79-83, 1987.Hunter, J. A. H. 和 Madachy, J. S. 数学消遣。 New York: Dover, pp. 33-34, 1975.Kraitchik, M. "Latin Squares." §7.11 in 数学娱乐。 New York: W. W. Norton, p. 178, 1942.Lindner, C. C. 和 Rodger, C. A. 设计理论。 Boca Raton, FL: CRC Press, 1997.MacMahon, P. A. 组合分析，第 1 卷。 London: Cambridge University Press, 1915.McKay, B. D. 和 Rogoyski, E. "Latin Squares of Order 10." Electronic J. Combinatorics 2, No. 1, R3, 1-4, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1r3.html.McKay, B. D. 和 Wanless, I. M. "On the Number of Latin Squares." Ann. Combin. 9, 335-344, 2005.McKay, B. D. "Latin Squares." http://users.cecs.anu.edu.au/~bdm/data/latin.html.Nechvatal, J. R. "Asymptotic Enumeration of Generalised Latin Rectangles." Util. Math. 20, 273-292, 1981.Norton, H. W. "The 7×7 Squares." Ann. Eugenics 9, 269-307, 1939.Rohl, J. S. 通过 Pascal 递归。 Cambridge, England: Cambridge University Press, pp. 162-165, 1984.Ryser, H. J. "Latin Rectangles." §3.3 in 组合数学。 Buffalo, NY: Math. Assoc. Amer., pp. 35-37, 1963.Sade, A. "Enumération des carrés latins. Application au 7ème ordre. Conjectures pour les ordres supérieurs." 8 pp. Marseille, France: Privately published, 1948.Saxena, P. N. "A Simplified Method of Enumerating Latin Squares by MacMahon's Differential Operators; II. The 7×7 Latin Squares." J. Indian Soc. Agricultural Statist. 3, 24-79, 1951.Shao, J.-Y. 和 Wei, W.-D. "A Formula for the Number of Latin Squares." Disc. Math. 110, 293-296, 1992.Sloane, N. J. A. 序列 A000479, A002860/M2051, A000315/M3690, A040082, 和 A072377 在 "整数序列在线百科全书" 中。Tarry, G. "Le problème de 36 officiers." Compte Rendu de l'Assoc. Français Avanc. Sci. Naturel 1, 122-123, 1900.Tarry, G. "Le problème de 36 officiers." Compte Rendu de l'Assoc. Français Avanc. Sci. Naturel 2, 170-203, 1901.Wells, M. B. "The Number of Latin Squares of Order Eight." J. Combin. Th. 3, 98-99, 1967.

在 Wolfram|Alpha 上被引用

拉丁方阵

请这样引用

Weisstein, Eric W. "拉丁方阵。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/LatinSquare.html

学科分类