A003109 -id:A003109 - cp's OEIS frontend

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

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

			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.

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

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

Bisection of A006609.

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

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)

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

A003112 Permanent of Schur's matrix of order 2n+1.

Original entry on oeis.org

1, -3, -5, -105, 81, 6765, 175747, 30375, 25219857, 142901109, 4548104883, -31152650265, -5198937484375, 65230244418933, -1300425712598285, 126691467546591, 868088125376401545, -15139017417029296875

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 121.

R. L. Graham and D. H. Lehmer, On the Permanent of Schur's Matrix, Jour. Australian Math. Soc. 21 (series A) (1976), 487-497.
R. L. Graham and D. H. Lehmer, On the Permanent of Schur's Matrix, annotated scanned copy of pages 496-497 only. [When Ron Graham showed me the first draft of this article in 1974, I pointed out that he and Dick Lehmer had overlooked the fact that this same sequence had appeared a year earlier in another Lehmer article! - _N. J. A. Sloane_, Sep 13 2018]
D. H. Lehmer, Some properties of circulants, J. Number Theory 5 (1973), 43-54. (See page 48.)
Eric Weisstein's World of Mathematics, Schur Matrix

Cf. A003109, A003110.

GrayInsert[n_] := Block[{q = n, j = 1}, While[ EvenQ[q], q /= 2; j++]; {j, (-1)^((q - 1)/2)}];abs2[x_] := Re[x]^2 + Im[x]^2;Schur[n_, prec_] :=  Block[{xi = N[E^(2 Pi* I/n), prec], m, i, j, rowsum, sum = 0}, m = Table[xi^Mod[i j, n], {i, n - 2}, {j, (n - 1)/2}]; rowsum = Table[xi^(-j) + N[1/2, prec], {j, (n - 1)/2}]; sum = abs2[Times @@ rowsum]; Do[gi = GrayInsert[i]; rowsum += gi[[2]]* m[[gi[[1]]]]; sum += N[(-1)^i* abs2[Times @@ rowsum], prec], {i, 2^(n - 2) - 1}]; -Round[n *2* sum]] /; OddQ[n]; Do[ Print[{n, Schur[n, n+1]}], {n, 1, 16}] (* copied the necessary Mathematica coding from Prof. Ilan Vardi, Robert G. Wilson v, Apr 19 2020 *)

permRWNb(a)=n=matsize(a)[1];if(n==1,return(a[1,1]));sg=1;in=vectorv(n);x=in;x=a[,n]-sum(j=1,n,a[,j])/2;p=prod(i=1,n,x[i]);for(k=1,2^(n-1)-1,sg=-sg;j=valuation(k,2)+1;z=1-2*in[j];in[j]+=z;x+=z*a[,j];p+=prod(i=1,n,x[i],sg));return(2*(2*(n%2)-1)*p)
for(k=1,12,n=2*k-1;z=exp(2*Pi*I/n);a=matrix(n,n,i,j,z^((i-1)*(j-1)));print1(round(real(permRWNb(a)))",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), May 17 2007

for(k=1, 12, a=matrix(2*k-1, 2*k-1, i, j, exp(2*Pi*I*(i-1)*(j-1)/(2*k-1))); print1(round(real(matpermanent(a)))", ")) \\ Vaclav Kotesovec, Aug 12 2021

a(n) = (-1)^n * (2*n+1) * (A003109(n) - A003110(n)). - Sean A. Irvine, Jan 31 2015

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 17 2007
a(15)-a(16) from Vaclav Kotesovec, Dec 11 2013
a(17) from Vaclav Kotesovec, Aug 19 2021

A003110 a(n) = number of special odd permutations of 2*n+1.

Original entry on oeis.org

0, 2, 2, 108, 2028, 32870, 1213110, 46493784, 2310521000, 137466038346, 9842687925450, 832295357128500

Offset: 1

N. J. A. Sloane

a(n) is the number of odd permutations, pi(0),...,pi(2*n), of 0,...,2*n such that pi(0) = 0 and p(k) = k + pi(k) (mod 2*n+1), k=0,...,2*n is also a permutation of 0,...,2*n. - Sean A. Irvine, Jan 31 2015

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

Cf. A003109 (special even permutations), A003110 (total).

Name clarified and offset corrected by Sean A. Irvine, Jan 31 2015
a(8)-a(9) from Sean A. Irvine, Jan 31 2015
a(10)-a(12) from Vaclav Kotesovec, May 17 2019 (using the terms of A003111 and A003112)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A003112 Permanent of Schur's matrix of order 2n+1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A003110 a(n) = number of special odd permutations of 2*n+1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions