|
%I M3069 #66 Jul 22 2023 07:06:31
%S 1,1,3,19,225,3441,79259,2424195,94471089,4613520889,275148653115,
%T 19686730313955,1664382756757625
%N Number of complete mappings of the cyclic group Z_{2n+1}.
%C A complete mapping of a cyclic group (Z_n,+) is a permutation f(x) of Z_n such that f(0)=0 and such that f(x)-x is also a permutation.
%C a(n)=TSQ(n)/n where TSQ(n) is the number of solutions of the toroidal semi-n-queen problem (A006717 is the sequence TSQ(2k-1)).
%C Stated another way, this is the number of "good" permutations on 2n+1 elements (see A006717) that start with 0. [Novakovich]. - _N. J. A. Sloane_, Feb 22 2011
%D Anthony B. Evans, Orthomorphism Graphs of Groups, vol. 1535 of Lecture Notes in Mathematics, Springer-Verlag, 1991.
%D Y. P. Shieh, Partition strategies for #P-complete problems with applications to enumerative combinatorics, PhD thesis, National Taiwan University, 2001.
%D Y. P. Shieh, J. Hsiang and D. F. Hsu, On the enumeration of Abelian k-complete mappings, Vol. 144 of Congressus Numerantium, 2000, pp. 67-88.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. Cavenagh and I. M. Wanless, <a href="https://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 Sean Eberhard, F. Manners, R. Mrazovic, <a href="http://arxiv.org/abs/1510.05987">Additive triples of bijections, or the toroidal semiqueens problem</a>, arXiv preprint arXiv:1510.05987 [math.CO], 2015-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 J. Hsiang, D. F. Hsu and Y. P. Shieh, <a href="https://doi.org/10.1016/S0012-365X(03)00176-6">On the hardness of counting problems of complete mappings</a>, Discrete Math., 277 (2004), 87-100.
%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 D. H. Lehmer, <a href="http://dx.doi.org/10.1016/0022-314X(73)90056-5">Some properties of circulants</a>, J. Number Theory 5 (1973), 43-54.
%H B. D. McKay, J. C. McLeod and I. M. Wanless, <a href="https://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 S. V. S. Ranganathan, D. Divsalar, R. D. Wesel, <a href="http://arxiv.org/abs/1504.04975">On the Girth of (3, L) Quasi-Cyclic LDPC Codes based on Complete Protographs</a>, arXiv preprint arXiv:1504.04975 [cs.IT], 2015.
%H Y. P. Shieh, <a href="http://turing.csie.ntu.edu.tw/~arping/cm">Cyclic complete mappings counting problems</a>
%H D. S. Stones and I. M. Wanless, <a href="https://doi.org/10.1016/j.ffa.2010.04.001">Compound orthomorphisms of the cyclic group</a>, Finite Fields Appl. 16 (2010), 277-289.
%H D. S. Stones, I. M. Wanless, <a href="https://doi.org/10.1007/s00026-012-0137-6">A congruence connecting Latin rectangles and partial orthomorphisms</a>, Ann. Comb. 16, No. 2, 349-365 (2012).
%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 3; b(n)=-2 mod n in n is prime; b(n) is divisible by n 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]. - From Ian Wanless, Jul 30 2010
%F a(n) = A003109(n) + A003110(n). - _Sean A. Irvine_, Jan 30 2015
%F Conjecture: a(n) = A006609(2*n+2), n>0. - _Sean A. Irvine_, Jan 30 2015
%F From _Vaclav Kotesovec_, Jul 22 2023: (Start)
%F a(n) ~ exp(-1/2) * (2*n)!^2 / (2*n + 1)^(2*n - 1). [Eberhard, Manners, Mrazovic, 2016, Theorem 1.3, n->2*n+1]
%F a(n) ~ Pi * 2^(2*n + 3) * n^(2*n + 2) / exp(4*n + 3/2). (End)
%e f(x)=2x in (Z_7,+) is a complete mapping of Z_7 since f(0)=0 and f(x)-x (=x) is also a permutation of Z_7.
%Y Cf. A006717, A071607, A071608, A071706, A006204, A006609, A003109, A003110.
%K nonn,nice,more
%O 0,3
%A _N. J. A. Sloane_
%E More terms from J. Hsiang, D. F. Hsu and Y. P. Shieh (arping(AT)turing.csie.ntu.edu.tw), Jun 03 2002
%E a(12) from Yuh-Pyng Shieh (arping(AT)gmail.com), Jan 10 2006
|
