主題
Search

拉丁矩形


一個 k×n 拉丁矩形 是一個 k×n 矩陣,其元素 a_(ij) in {1,2,...,n} 使得每行和每列的條目都是不同的。如果 k=n,則得到 拉丁方格 的特殊情況。一個標準化的拉丁矩形的第一行是 {1,2,...,n} ,第一列是 {1,2,...,k}。令 L(k,n) 為標準化 k×n 拉丁矩形的數量,那麼 k×n 拉丁矩形的總數是

 N(k,n)=(n!(n-1)!L(k,n))/((n-k)!)
(1)

(McKay 和 Rogoyski 1995),其中 n!階乘。Kerewala (1941) 找到了 遞推關係 用於 L(3,n),Athreya 等人 (1980) 找到了 公式 用於求和 L(4,n)

Godsil 和 McKay (1990) 找到了 L(o(n^(6/7)),n) 的漸近值。 McKay 和 Rogoyski (1995) 在下表中給出了 k×n 拉丁矩形的數量。條目 L(1,n)L(n,n) 被省略,因為

L(1,n)=1
(2)
L(n,n)=L(n-1,n),
(3)

但為了清晰起見,包含了 L(1,1)L(2,1) 。 OEIS A001009 以“環繞”系列的形式給出了 L(k,n) 的值。

nkL(k,n)
111
211
321
423
434
5211
5346
5456
6253
631064
646552
659408
72309
7335792
741293216
7511270400
7616942080
822119
831673792
84420909504
8527206658048
86335390189568
87535281401856
9216687
93103443808
94207624560256
95112681643083776
9612952605404381184
97224382967916691456
98377597570964258816
102148329
1038154999232
104147174521059584
105746988383076286464
106870735405591003709440
107177144296983054185922560
1084292039421591854273003520
1097580721483160132811489280

使用 探索

參考文獻

Athreya, K. B.; Pranesachar, C. R.; and Singhi, N. M. "關於拉丁矩形的數量和 L(K_(r,s)) 的色多項式." Europ. J. Combin. 1, 9-17, 1980.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC 組合設計手冊. Boca Raton, FL: CRC Press, 1996.Godsil, C. D. and McKay, B. D. "拉丁矩形的漸近計數." J. Combin. Th. Ser. B 48, 19-44, 1990.Kerawla, S. M. "用差分方程列舉深度為三的拉丁矩形" [sic]. Bull. Calcutta Math. Soc. 33, 119-127, 1941.McKay, B. D. and Rogoyski, E. "10 階拉丁方格." Electronic J. Combinatorics 2, No. 1, N3, 1-4, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1n3.html.Ryser, H. J. "拉丁矩形." §3.3 in 組合數學. Buffalo, NY: Math. Assoc. of Amer., pp. 35-37, 1963.Sloane, N. J. A. Sequence A001009 in "整數序列線上百科全書."

在 中被引用

拉丁矩形

請引用為

Weisstein, Eric W. "拉丁矩形。" 來自 —— 資源。 https://mathworld.tw/LatinRectangle.html

主題分類