%I M3005 #99 Aug 28 2023 08:22:31
%S 1,3,15,133,2025,37851,1030367,36362925,1606008513,87656896891,
%T 5778121715415,452794797220965,41609568918940625
%N Number of ways of arranging 2n+1 nonattacking semi-queens on a (2n+1) X (2n+1) toroidal board.
%C Also the number of "good" permutations on 2n+1 elements [Novakovich]. - _N. J. A. Sloane_, Feb 22 2011
%C Also the number of transversals of a cyclic Latin square of order 2n+1 and the number of orthomorphisms of the cyclic group of order 2n+1. - _Ian Wanless_, Oct 07 2001
%C Also the number of complete mappings of a cyclic group of order 2n+1; also (2n+1) times the number of "standard" complete mappings of cyclic group of order 2n+1. - Jieh Hsiang, D. Frank Hsu and Yuh Pyng Shieh (arping(AT)turing.csie.ntu.edu.tw), May 08 2002
%C See A003111 for further information.
%C A very simple model using only addition mod n: Let i=index vector (0,1,..n-1) on any set of n distinct values, and j=index vector for the values after reordering. Then j = (i + d) mod n, where d is the vector of distances moved, and a(n) = number of reorderings that give an equidistributed set d (i.e., 1 instance of each distance moved). Since a(n)=0 for all even n, taking only odd n gives the sequence above - _Ross Drewe_, Sep 03 2017
%C All broken diagonals and antidiagonals of cyclic Latin square are transversals, so a(n) >= 2*n for all n > 1 for which cyclic Latin squares exist. - _Eduard I. Vatutin_, Mar 23 2022
%D Yuh Pyng Shieh, Jieh Hsiang and D. Frank Hsu, On the enumeration of Abelian k-complete mappings, vol. 144 of Congressus Numerantium, 2000, pp. 67-88.
%D Yuh Pyng Shieh, Partition Strategies for #P-complete problem with applications to enumerative combinatorics, PhD thesis, National Taiwan University, 2001.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 118.
%H Christian Carley, <a href="https://scholarworks.boisestate.edu/math_undergraduate_theses/12">The Name Tag Problem</a>, Mathematics Undergraduate Theses (Boise State University, 2019).
%H N. J. Cavenagh and I. M. Wanless, <a href="http://dx.doi.org/10.1016/j.dam.2009.09.006">On the number of transversals in Cayley tables of cyclic groups</a>, Disc. Appl. Math. 158 (2010), 136-146.
%H S. Eberhard, F. Manners, and R. Mrazovic, <a href="https://arxiv.org/abs/1510.05987">Additive Triples of Bijections, or the Toroidal Semiqueens Problem </a>, arxiv:1510.05987, [math.CO], 2016.
%H Jieh Hsiang, YuhPyng Shieh, and YaoChiang Chen, <a href="https://fr.slideserve.com/uta/cyclic-complete-mappings-counting-problems">Cyclic Complete Mappings Counting Problems</a>, National Taiwan University 2014/8/21.
%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013.
%H N. Yu. Kuznetsov, <a href="https://doi.org/10.1007/s10559-016-9799-0">Using the Monte Carlo Method for Fast Simulation of the Number of "Good" Permutations on the SCIT-4 Multiprocessor Computer Complex</a>, Cybernetics and Systems Analysis, January 2016, Volume 52, Issue 1, pp 52-57.
%H B. D. McKay, J. C. McLeod and I. M. Wanless, <a href="http://dx.doi.org/10.1007/s10623-006-0012-8">The number of transversals in a Latin square</a>, Des. Codes Cryptogr., 40, (2006) 269-284.
%H D. Novakovic, <a href="https://doi.org/10.1007/BF02678671">Computation of the number of complete mappings for permutations</a>, Cybernetics & System Analysis, No. 2, v. 36 (2000), pp. 244-247.
%H Kevin Pratt, <a href="https://arxiv.org/abs/1609.09585">Closed-Form Expressions for the n-Queens Problem and Related Problems</a>, arXiv:1609.09585 [cs.DM], 2016.
%H D. S. Stones and I. M. Wanless, <a href="http://dx.doi.org/10.1016/j.ffa.2010.04.001">Compound orthomorphisms of the cyclic group</a>, Finite Fields Appl. 16 (2010), 277-289.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QueensProblem.html">Queens Problem.</a>
%F Suppose n is odd and let b(n)=a((n-1)/2). Then b(n) is odd; if n>3 and n is not 1 mod 3 then b(n) is divisible by 3n; b(n)=-2n mod n^2 in n is prime; b(n) is divisible by n^2 if n is composite; b(n) is asymptotically in between 3.2^n and 0.62^n n!. [Cavenagh, Wanless], [McKay, McLeod, Wanless], [Stones, Wanless] - _Ian Wanless_, Jul 30 2010
%F b(n) is asymptotic to e^(-1/2) n!^2/n^(n-1) [Eberhard, Manners, Mrazovic]. - _Sam Spiro_, Apr 16 2019; corrected by _Sean Eberhard_, Jul 21 2023
%F a(n) = (2*n+1) * A003111(n). - _Andrew Howroyd_, Sep 28 2020
%o (MATLAB) k = 6; A = zeros(1,k); for i = 1:k; n = 2*i-1; x = [0: n-1]; allP = perms(x); T = size(allP,1); X = repmat(x, T, 1); Y = mod(X + allP, n); Y = sort(Y, 2); L = ~(sum(Y ~= X, 2)); A(i) = sum(L); end; A
%o % 1st 6 terms by testing all n! possible distance vectors
%o % _Ross Drewe_, Sep 03 2017
%Y Cf. A003111, A007705.
%K nonn,more,nice
%O 0,2
%A _N. J. A. Sloane_
%E More terms from Jieh Hsiang, D. Frank Hsu and Yuh Pyng Shieh (arping(AT)turing.csie.ntu.edu.tw), May 08 2002
%E a(12) added from A003111 by _N. J. A. Sloane_, Mar 29 2007
%E Definition clarified by _Vaclav Kotesovec_, Sep 16 2014