主題
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, 數獨

使用 探索

參考文獻

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.

在 上被引用

拉丁方陣

請這樣引用

Weisstein, Eric W. "拉丁方陣。" 來自 Web 資源。 https://mathworld.tw/LatinSquare.html

學科分類