主题
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. "拉丁矩形。" 来自 MathWorld—— 资源。 https://mathworld.net.cn/LatinRectangle.html

主题分类