Additive triples of bijections, or the toroidal semiqueens problem

被引:11
作者
Eberhard, Sean
Manners, Freddie [1 ]
Mrazovic, Rudi [2 ]
机构
[1] Stanford Univ, Dept Math, 450 Serra Mall,Bldg 380, Stanford, CA 94305 USA
[2] Univ Zagreb, Dept Math, Bijenicka Cesta 30, Zagreb 10090, Croatia
关键词
Hardy-Littlewood circle method; transversals in Latin squares; permutations; FAST SIMULATION; NUMBER;
D O I
10.4171/JEMS/841
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We prove an asymptotic for the number of additive triples of bijections {1, ..., n} -> Z/nZ, that is, the number of pairs of bijections pi(1), pi(2) : {1, ..., n} -> Z/nZ such that the point-wise sum pi(1) + pi(2) is also a bijection. This problem is equivalent to counting the number of orthomorphisms or complete mappings of Z/nZ, to counting the number of arrangements of n mutually nonattacking semiqueens on an n x n toroidal chessboard, and to counting the number of transversals in a cyclic Latin square. The method of proof is a version of the Hardy-Littlewood circle method from analytic number theory, adapted to the group (Z/nZ)(n).
引用
收藏
页码:441 / 463
页数:23
相关论文
共 17 条
[1]  
[Anonymous], 2009, ANAL COMBINATORICS, DOI [DOI 10.1017/CBO9780511801655, 10.1017/CBO9780511801655]
[2]  
Bona Miklos, 2015, Handbook of Enumerative Combinatorics, Discrete Mathematics and its Applications
[3]   On the number of transversals in Cayley tables of cyclic groups [J].
Cavenagh, Nicholas J. ;
Wanless, Ian M. .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (02) :136-146
[4]  
Cooper C., 2000, DATA REC STORAGE PRO, V213, P15
[5]  
Cooper C, 1999, KIBERNET SISTEM ANAL, V5, P10
[6]  
Cooper C., 1996, THEORY PROBAB MATH S, V53, P77
[7]   On the maximum number of Latin transversals [J].
Glebov, Roman ;
Luria, Zur .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2016, 141 :136-146
[8]  
Kovalenko I. N., 1996, KIBERNET SISTEM ANAL, V1, P188
[9]   Estimating the number of good permutations by a modified fast simulation method [J].
Kuznetsov N.Yu. .
Cybernetics and Systems Analysis, 2008, 44 (04) :547-554
[10]   Applying fast simulation to find the number of good permutations [J].
Kuznetsov N.Yu. .
Cybernetics and Systems Analysis, 2007, 43 (6) :830-837