On the number of Latin squares

被引:108
作者
McKay, Brendan D. [1 ]
Wanless, Ian M.
机构
[1] Australian Natl Univ, Dept Comp Sci, Canberra, ACT 0200, Australia
[2] Charles Darwin Univ, Sch Engn & Logist, Darwin, NT 0909, Australia
关键词
Latin square; enumeration; 1-factorisation; permanent; regular bipartite graph;
D O I
10.1007/s00026-005-0261-7
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We ( 1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, ( 2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f ! where f is a particular integer close to 1/2 n, ( 3) provide a formula for the number of Latin squares in terms of permanents of (+ 1; 1)- matrices, ( 4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 <= k <= n <= 11, ( 5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases.
引用
收藏
页码:335 / 344
页数:10
相关论文
共 22 条
[1]   HOW MANY LATIN SQUARES ARE THERE [J].
ALTER, R .
AMERICAN MATHEMATICAL MONTHLY, 1975, 82 (06) :632-634
[2]  
[Anonymous], 1971, ELEMENTS COMBINATORI
[3]   NUMBER OF 9 X 9 LATIN SQUARES [J].
BAMMEL, SE ;
ROTHSTEIN, J .
DISCRETE MATHEMATICS, 1975, 11 (01) :93-95
[4]  
BROWN JW, 1968, J COMB THEORY, V5, P177
[5]  
CAYLEY A, 1890, MESS MATH, V19, P135
[6]  
Euler L., 1782, VERHANDELINGEN UITGE, V9, P85
[7]  
Frolov M., 1890, J MATH SPEC, V4, P8
[8]  
Frolov M, 1890, J MATH SPEC, V4, P25
[9]   ASYMPTOTIC ENUMERATION OF LATIN RECTANGLES [J].
GODSIL, CD ;
MCKAY, BD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (01) :19-44
[10]  
Macmahon P. A., 1915, COMBINATORY ANAL