A343867 -id:A343867 - cp's OEIS frontend

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

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

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

			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)

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.

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.

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

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

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

A342990 Number of horizontally or vertically semicyclic diagonal Latin squares of order 2n+1.

Original entry on oeis.org

1, 0, 240, 20160, 0, 319334400, 2167003238400, 0, 2943669154922496000, 5253122016055001088000, 0, 144827547726179682893168640000, 1214667347283206181421056000000000, 0, 184737047979495031539522261089255424000000, 3555700708206908663181998415125686517760000000, 0

Offset: 0

Eduard I. Vatutin, Jan 27 2022

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

			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=14 ==  1 (mod 13))
   3  4  5  6  7  8  9 10 11 12  0  1  2  (d=16 ==  3 (mod 13))
   5  6  7  8  9 10 11 12  0  1  2  3  4  (d=18 ==  5 (mod 13))
   7  8  9 10 11 12  0  1  2  3  4  5  6  (d=20 ==  7 (mod 13))
   9 10 11 12  0  1  2  3  4  5  6  7  8  (d=22 ==  9 (mod 13))
  11 12  0  1  2  3  4  5  6  7  8  9 10  (d=24 == 11 (mod 13))
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)

Eduard I. Vatutin, About the horizontally and vertically semicyclic diagonal Latin squares enumeration (in Russian).
E. 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)
Eduard I. Vatutin, Numerical formula between number of horizontally or vertically semicyclic diagonal Latin squares and number of toroidal n-queens problem solutions (in Russian).
Index entries for sequences related to Latin squares and rectangles.

Cf. A007705, A071607, A338562, A343867.

a(n) = A071607(n) * (2*n+1)!.

a(n) = A007705(n) * (2n)!. - Eduard I. Vatutin, Mar 15 2024

A338620 Number of pandiagonal Latin squares of order 2n+1 with the first row in ascending order.

Original entry on oeis.org

1, 0, 2, 4, 0, 8, 12386, 0

Offset: 0

Eduard I. Vatutin, Nov 04 2020

A pandiagonal Latin square is a Latin square in which the diagonal, antidiagonal and all broken diagonals and antidiagonals are transversals.
For orders n = 5, 7 and 11 all pandiagonal Latin squares are cyclic, so a(n) = A123565(2n+1) for n < 6. For n=6 (order 13), this is not true and there are 12386 inequivalent squares; of these 10 are cyclic (in all directions) and 1560 are semi-cyclic (A343867).
Pandiagonal Latin squares exist only for odd orders not divisible by 3. This is because the positions of each symbol are a solution to the toroidal n-queens problem which only has solutions for these sizes. - Andrew Howroyd, May 26 2021

			Example of a cyclic pandiagonal Latin square of order 5:
  0 1 2 3 4
  2 3 4 0 1
  4 0 1 2 3
  1 2 3 4 0
  3 4 0 1 2
Example of a cyclic pandiagonal Latin square of order 7:
  0 1 2 3 4 5 6
  2 3 4 5 6 0 1
  4 5 6 0 1 2 3
  6 0 1 2 3 4 5
  1 2 3 4 5 6 0
  3 4 5 6 0 1 2
  5 6 0 1 2 3 4
Example of a cyclic pandiagonal Latin square of order 11:
   0  1  2  3  4  5  6  7  8  9 10
   2  3  4  5  6  7  8  9 10  0  1
   4  5  6  7  8  9 10  0  1  2  3
   6  7  8  9 10  0  1  2  3  4  5
   8  9 10  0  1  2  3  4  5  6  7
  10  0  1  2  3  4  5  6  7  8  9
   1  2  3  4  5  6  7  8  9 10  0
   3  4  5  6  7  8  9 10  0  1  2
   5  6  7  8  9 10  0  1  2  3  4
   7  8  9 10  0  1  2  3  4  5  6
   9 10  0  1  2  3  4  5  6  7  8
For order 13 there is a square
   7  1  0  3  6  5 12  2  8  9 10 11  4
   2  3  4 10  0  7  6  9 12 11  5  8  1
   4 11  1  7  8  9 10  3  6  0 12  2  5
   6  5  8 11 10  4  7  0  1  2  3  9 12
   8  9  2  5 12 11  1  4  3 10  0  6  7
   3  6 12  0  1  2  8 11  5  4  7 10  9
  10  0  3  2  9 12  5  6  7  8  1  4 11
   1  7 10  4  3  6  9  8  2  5 11 12  0
  11  4  5  6  7  0  3 10  9 12  2  1  8
   5  8  7  1  4 10 11 12  0  6  9  3  2
  12  2  9  8 11  1  0  7 10  3  4  5  6
   9 10 11 12  5  8  2  1  4  7  6  0  3
   0 12  6  9  2  3  4  5 11  1  8  7 10
that is pandiagonal but not cyclic (Dabbaghian and Wu).

A. O. L. Atkin, L. Hay, and R. G. Larson, Enumeration and construction of pandiagonal Latin squares of prime order, Computers & Mathematics with Applications, Volume. 9, Iss. 2, 1983, pp. 267-292.
Vahid Dabbaghian and Tiankuang Wu, Constructing non-cyclic pandiagonal Latin squares of prime orders, Journal of Discrete Algorithms 30, 2015.
Vahid Dabbaghian and Tiankuang Wu, Constructing Pandiagonal Latin Squares from Linear Cellular Automaton on Elementary Abelian Groups, Journal of Combinatorial Designs 23(5).

Cf. A071607 (rows are cyclic), A123565, A342306, A343867 (semicyclic).

a(n) >= A123565(2n+1) + A343867(n). - Andrew Howroyd, May 26 2021

a(n) = A342306(n) / (2n+1)!. - Eduard I. Vatutin, Jun 13 2021

Zero terms for even orders removed by Andrew Howroyd, May 26 2021

A343868 Number of semicyclic Latin squares of order n with the first row in ascending order.

Original entry on oeis.org

0, 0, 0, 8, 40, 338, 1512, 11368, 84960, 828972, 7291900, 85823668, 958954152, 12930529446, 176651211776, 2631044069296, 41847091313152

Offset: 1

Andrew Howroyd, May 08 2021

A semicyclic Latin square is cyclic in one or more directions but not in every direction. Cyclic Latin squares which are cyclic in essentially every direction are excluded. A direction here means any constant row and column displacement on the torus. See the reference in A343867 for additional information.

Each symbol occupies the same pattern of squares up to translation on the torus.

			The permutation 164253 can be shown in a 6 X 6 grid:
    X . . . . .
    . . . . . X
    . . . X . .
    . X . . . .
    . . . . X .
    . . X . . .
This permutation gives the following 4 semicyclic squares.
    1 2 3 4 5 6   1 4 2 5 3 6   1 4 3 6 2 5   1 4 5 2 3 6
    2 3 4 5 6 1   2 5 3 6 4 1   3 6 2 5 4 1   2 5 6 3 4 1
    4 5 6 1 2 3   3 6 4 1 5 2   5 2 4 1 3 6   6 3 4 1 2 5
    6 1 2 3 4 5   4 1 5 2 6 3   4 1 6 3 5 2   4 1 2 5 6 3
    3 4 5 6 1 2   5 2 6 3 1 4   6 3 5 2 1 4   5 2 3 6 1 4
    5 6 1 2 3 4   6 3 1 4 2 5   2 5 1 4 6 3   3 6 1 4 5 2
In the third example, moving one cell down and two across increases the cell value by 1 (cyclically) and in the fourth example the displacement is 3 rows down and 2 across. Symbols can then be rearranged to give 4 distinct semicyclic squares with the first row in ascending order.

Andrew Howroyd, Order 6 semicyclic Latin squares
Andrew Howroyd, PARI Program

Cf. A000010 (phi), A001615, A003111, A343867.

PARI
```
\\ See Links
```

a(n) >= 2*((n-1)! - phi(n)).

a(p) = 2*(p-1)! + (p-1)*(A003111((p-1)/2) - p) for odd prime p.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A342990 Number of horizontally or vertically semicyclic diagonal Latin squares of order 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A338620 Number of pandiagonal Latin squares of order 2n+1 with the first row in ascending order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A343868 Number of semicyclic Latin squares of order n with the first row in ascending order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula