login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003111 Number of complete mappings of the cyclic group Z_{2n+1}.
(Formerly M3069)
4
1, 1, 3, 19, 225, 3441, 79259, 2424195, 94471089, 4613520889, 275148653115, 19686730313955, 1664382756757625 (list; graph; refs; listen; history; text; internal format)
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

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.

Anthony B. Evans, Orthomorphism Graphs of Groups, vol. 1535 of Lecture Notes in Mathematics, Springer-Verlag, 1991.

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.

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, (2000) Computation of the number of complete mappings for permutations. Cybernetics & System Analysis, No. 2, v. 36, pp. 244-247.

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

D. S. Stones and I. M. Wanless, Compound orthomorphisms of the cyclic group, Finite Fields Appl. 16 (2010), 277-289.

LINKS

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

Dariush Divsalar, Sudarsan V. S. Ranganathan, Richard D. Wesel, On the Girth of (3,L) Quasi-Cyclic LDPC Codes based on Complete Protographs, arXiv preprint, 2015.

Sean Eberhard, F Manners, R Mrazovic, Additive triples of bijections, or the toroidal semiqueens problem, arXiv preprint arXiv:1510.05987, 2015

D. H. Lehmer, Some properties of circulants, J. Number Theory 5 (1973), 43-54.

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.04975v2, 2015

Y. P. Shieh, Cyclic complete mappings counting problems

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

EXAMPLE

f(x)=2x in (Z_7,+) is a complete mapping of Z_7 since that f(0)=0 and that 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 18:28 EST 2019. Contains 319365 sequences. (Running on oeis4.)