|
|
A003111
|
|
Number of complete mappings of the cyclic group Z_{2n+1}.
(Formerly M3069)
|
|
6
|
|
|
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
|
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
|
|
|
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) ~ 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
|
|
|
KEYWORD
|
nonn,nice,more
|
|
AUTHOR
|
|
|
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
|
|
|
|