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

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

Offset: 1

Author

Andrew Howroyd, May 08 2021

Keywords

• nonn
• more

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

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

Programs

PARI

\\ See Links

Formula

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

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