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

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

Offset

0,3

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

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

Table of n, a(n) for n=0..12.

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, 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, 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, I. M. Wanless, A congruence connecting Latin rectangles and partial orthomorphisms, Ann. Comb. 16, No. 2, 349-365 (2012).

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

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

Conjecture: 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)

Example

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.

Crossrefs

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

Sequence in context: A166380 A136652 A136504 * A160888 A126444 A198046

Adjacent sequences: A003108 A003109 A003110 * A003112 A003113 A003114

Keyword

nonn,nice,more

Author

N. J. A. Sloane

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

Status

approved