A003111 Number of complete mappings of the cyclic group Z_{2n+1}.

1, 1, 3, 19, 225, 3441, 79259, 2424195, 94471089, 4613520889, 275148653115, 19686730313955, 1664382756757625

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• more

Comments

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.

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)).

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

Examples

			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.
		

References

• Anthony B. Evans, Orthomorphism Graphs of Groups, vol. 1535 of Lecture Notes in Mathematics, Springer-Verlag, 1991.
• Y. P. Shieh, Partition strategies for #P-complete problems with applications to enumerative combinatorics, PhD thesis, National Taiwan University, 2001.
• 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.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• N. J. Cavenagh and I. M. Wanless, On the number of transversals in Cayley tables of cyclic groups, Disc. Appl. Math. 158 (2010), 136-146.
• Sean Eberhard, F. Manners, and R. Mrazovic, Additive triples of bijections, or the toroidal semiqueens problem, arXiv preprint arXiv:1510.05987 [math.CO], 2015-2016.
• Jieh Hsiang, YuhPyng Shieh, and YaoChiang Chen, Cyclic Complete Mappings Counting Problems, National Taiwan University 2014/8/21.
• J. Hsiang, D. F. Hsu and Y. P. Shieh, On the hardness of counting problems of complete mappings, Discrete Math., 277 (2004), 87-100.
• N. Yu. Kuznetsov, Using the Monte Carlo Method for Fast Simulation of the Number of "Good" Permutations on the SCIT-4 Multiprocessor Computer Complex, Cybernetics and Systems Analysis, January 2016, Volume 52, Issue 1, pp 52-57.
• D. H. Lehmer, Some properties of circulants, J. Number Theory 5 (1973), 43-54.
• B. D. McKay, J. C. McLeod and I. M. Wanless, The number of transversals in a Latin square, Des. Codes Cryptogr., 40, (2006) 269-284.
• D. Novakovic, Computation of the number of complete mappings for permutations, Cybernetics & System Analysis, No. 2, v. 36 (2000), pp. 244-247.
• S. V. S. Ranganathan, D. Divsalar, and R. D. Wesel, On the Girth of (3, L) Quasi-Cyclic LDPC Codes based on Complete Protographs, arXiv preprint arXiv:1504.04975 [cs.IT], 2015.
• Y. P. Shieh, Cyclic complete mappings counting problems
• D. S. Stones and I. M. Wanless, Compound orthomorphisms of the cyclic group, Finite Fields Appl. 16 (2010), 277-289.
• D. S. Stones and I. M. Wanless, A congruence connecting Latin rectangles and partial orthomorphisms, Ann. Comb. 16, No. 2, 349-365 (2012).

Crossrefs

Bisection of A006609.

Cf. A006717, A071607, A071608, A071706, A006204, A003109, A003110.

Formula

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]. - Ian Wanless, Jul 30 2010

a(n) = A003109(n) + A003110(n). - Sean A. Irvine, Jan 30 2015

a(n) = A006609(2*n+2), n>0. - Sean A. Irvine, Jan 30 2015

From Vaclav Kotesovec, Jul 22 2023: (Start)

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]

a(n) ~ Pi * 2^(2*n + 3) * n^(2*n + 2) / exp(4*n + 3/2). (End)

Extensions

More terms from J. Hsiang, D. F. Hsu and Y. P. Shieh (arping(AT)turing.csie.ntu.edu.tw), Jun 03 2002

a(12) from Yuh-Pyng Shieh (arping(AT)gmail.com), Jan 10 2006