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

1, 0, 2, 4, 0, 8, 348, 0, 8276, 43184, 0, 5602176, 78309000, 0, 20893691564, 432417667152, 0

Offset: 0

Author

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

Keywords

• nonn
• hard
• more

Comments

A strong complete mapping of a cyclic group (Z_n,+) is a permutation f(x) of Z_n such that f(0)=0 and that f(x)-x and f(x)+x are both permutations.

a(n) is the number of solutions of the toroidal n-queen problem (A007705) with 2n+1 queens and one queen in the top-left corner.

Also a(n) is the number of horizontally or vertically semicyclic diagonal Latin squares of order 2n+1 with the first row in ascending order. Horizontally semicyclic diagonal Latin square is a square where each row r(i) is a cyclic shift of the first row r(0) by some value d(i) (see example). Vertically semicyclic diagonal Latin square is a square where each column c(i) is a cyclic shift of the first column c(0) by some value d(i). Cyclic diagonal Latin squares (see A123565) fall under the definition of vertically and horizontally semicyclic diagonal Latin squares simultaneously, in this type of squares each row r(i) is obtained from the previous one r(i-1) using cyclic shift by some value d. Definition from A343867 includes this type of squares but not only it. - Eduard I. Vatutin, Jan 25 2022

Examples

			f(x)=2x in (Z_7,+) is a strong complete mapping of Z_7 since f(0)=0 and both f(x)-x (=x) and f(x)+x (=3x) are permutations of Z_7.
From _Eduard I. Vatutin_, Jan 25 2022: (Start)
Example of cyclic diagonal Latin square of order 13:
.
   0  1  2  3  4  5  6  7  8  9 10 11 12
   2  3  4  5  6  7  8  9 10 11 12  0  1  (d=2)
   4  5  6  7  8  9 10 11 12  0  1  2  3  (d=4)
   6  7  8  9 10 11 12  0  1  2  3  4  5  (d=6)
   8  9 10 11 12  0  1  2  3  4  5  6  7  (d=8)
  10 11 12  0  1  2  3  4  5  6  7  8  9  (d=10)
  12  0  1  2  3  4  5  6  7  8  9 10 11  (d=12)
   1  2  3  4  5  6  7  8  9 10 11 12  0  (d=1)
   3  4  5  6  7  8  9 10 11 12  0  1  2  (d=3)
   5  6  7  8  9 10 11 12  0  1  2  3  4  (d=5)
   7  8  9 10 11 12  0  1  2  3  4  5  6  (d=7)
   9 10 11 12  0  1  2  3  4  5  6  7  8  (d=9)
  11 12  0  1  2  3  4  5  6  7  8  9 10  (d=11)
.
Example of horizontally semicyclic diagonal Latin square of order 13:
.
   0  1  2  3  4  5  6  7  8  9 10 11 12
   2  3  4  5  6  7  8  9 10 11 12  0  1  (d=2)
   4  5  6  7  8  9 10 11 12  0  1  2  3  (d=4)
   9 10 11 12  0  1  2  3  4  5  6  7  8  (d=9)
   7  8  9 10 11 12  0  1  2  3  4  5  6  (d=7)
  12  0  1  2  3  4  5  6  7  8  9 10 11  (d=12)
   3  4  5  6  7  8  9 10 11 12  0  1  2  (d=3)
  11 12  0  1  2  3  4  5  6  7  8  9 10  (d=11)
   6  7  8  9 10 11 12  0  1  2  3  4  5  (d=6)
   1  2  3  4  5  6  7  8  9 10 11 12  0  (d=1)
   5  6  7  8  9 10 11 12  0  1  2  3  4  (d=5)
  10 11 12  0  1  2  3  4  5  6  7  8  9  (d=10)
   8  9 10 11 12  0  1  2  3  4  5  6  7  (d=8)
(End)
From _Eduard I. Vatutin_, Apr 09 2024: (Start)
Example of N-queens problem on toroidal board, N=2*2+1=5, a(2)=2, given by knight with (+1,+2) and (+1,+3) movement parameters starting from top left corner:
.
+-----------+ +-----------+
| Q . . . . | | Q . . . . |
| . . Q . . | | . . . Q . |
| . . . . Q | | . Q . . . |
| . Q . . . | | . . . . Q |
| . . . Q . | | . . Q . . |
+-----------+ +-----------+
.
Example of N-queens problem on toroidal board, N=2*3+1=7, a(3)=4, given by knight with (+1,+2), (+1,+3), (+1,+4), (+1,+5) movement parameters starting from top left corner:
.
+---------------+ +---------------+ +---------------+ +---------------+
| Q . . . . . . | | Q . . . . . . | | Q . . . . . . | | Q . . . . . . |
| . . Q . . . . | | . . . Q . . . | | . . . . Q . . | | . . . . . Q . |
| . . . . Q . . | | . . . . . . Q | | . Q . . . . . | | . . . Q . . . |
| . . . . . . Q | | . . Q . . . . | | . . . . . Q . | | . Q . . . . . |
| . Q . . . . . | | . . . . . Q . | | . . Q . . . . | | . . . . . . Q |
| . . . Q . . . | | . Q . . . . . | | . . . . . . Q | | . . . . Q . . |
| . . . . . Q . | | . . . . Q . . | | . . . Q . . . | | . . Q . . . . |
+---------------+ +---------------+ +---------------+ +---------------+
(End)
		

References

• Anthony B. Evans,"Orthomorphism Graphs of Groups", vol. 1535 of Lecture Notes in Mathematics, Springer-Verlag, 1991.
• 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.

Links

• Jieh Hsiang, Yuh Pyng Shieh, and Yao Chiang Chen, Cyclic complete mappings counting problems, in PaPS: Problems and Problem Sets for ATP Workshop in conjunction with CADE-18 and FLoC 2002.
• Jieh Hsiang, YuhPyng Shieh, and YaoChiang Chen, Cyclic Complete Mappings Counting Problems, National Taiwan University 2014/8/21.
• D. Novakovic, Computation of the number of complete mappings for permutations, Cybernetics & System Analysis, No. 2, v. 36 (2000), pp. 244-247.
• I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math. Monthly, 101 (1994), pp. 629-639.
• Eduard I. Vatutin, About the horizontally and vertically semicyclic diagonal Latin squares enumeration (in Russian).
• Eduard I. Vatutin, Special types of diagonal Latin squares, Cloud and distributed computing systems in electronic control conference, within the National supercomputing forum (NSCF - 2022). Pereslavl-Zalessky, 2023. pp. 9-18. (in Russian)
• Index entries for sequences related to Latin squares and rectangles.

Crossrefs

Cf. A007705, A051906, A123565, A338620, A342990, A343867.

Formula

a(n) = A007705(n) / (2*n+1).

a(n) = A342990(n) / (2*n+1)!. - Eduard I. Vatutin, Mar 10 2022

a(n) = A051906(2*n+1) / (2*n+1). - Eduard I. Vatutin, Apr 09 2024

Extensions

a(15)-a(16) added using A007705 by Andrew Howroyd, May 07 2021