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,3

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

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

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

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.

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

Example

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)

Crossrefs

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

Sequence in context: A103191 A324717 A295793 * A338620 A358645 A095059

Adjacent sequences: A071604 A071605 A071606 * A071608 A071609 A071610

Keyword

nonn,hard,more

Author

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

Extensions

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

Status

approved