A309283 Number of equivalence classes of X-based filling of diagonals in a diagonal Latin square of order n.

1, 1, 0, 0, 2, 2, 3, 3, 20, 20, 67, 67, 596, 596

Offset: 0

Author

Eduard I. Vatutin, Jul 06 2020

Keywords

• nonn
• more
• hard

Comments

Used for getting strong canonical forms (SCFs) of the diagonal Latin squares and for fast enumerating of the diagonal Latin squares based on equivalence classes.

K1 = |C[1]|*f[1] + |C[2]|*f[2] + ... + |C[m]|*f[m],

K2 = K1 * n!,

where m = a(n), number of equivalence classes for X-based filling of diagonals in a diagonal Latin square of order n;

C[i], corresponding equivalence classes with cardinalities |C[i]|, 1 <= i <= m;

f[i], the number of diagonal Latin squares corresponds to the each item from equivalence class C[i], 1 <= i <= m;

K1 = A274171(n), number of diagonal Latin squares of order n with fixed first row;

K2 = A274806(n), number of diagonal Latin squares of order n.

For all t>0 a(2*t) = a(2*t+1). - Eduard I. Vatutin, Aug 21 2020

a(14) >= 5225, a(15) >= 5225. - Natalia Makarova, Sep 12 2020

The number of solutions in an equivalence class with the main diagonal in ascending order is at most 4*2^r*r! where r = floor(n/2). This maximum is achieved for orders n >= 10. - Andrew Howroyd, Mar 27 2023

Examples

			For order n=4 there are a(4)=2 equivalence classes. First of them C[1] includes two X-based fillings of diagonals
   0..1  0..2
   .13.  .10.
   .02.  .32.
   2..3  1..3
and second C[2] also includes two X-based fillings of diagonals
   0..1  0..2
   .10.  .13.
   .32.  .02.
   2..3  1..3
It is easy to see that f[1] = 0 and f[2] = 1, so K1(4) = A274171(4) = 2*0 + 2*1 = 2 and K2(4) = A274806(4) = K1(4) * 4! = 2 * 24 = 48.
		

Links

• S. Kochemazov, O. Zaikin, E. Vatutin, and A. Belyshev, Enumerating Diagonal Latin Squares of Order Up to 9, Journal of Integer Sequences. Vol. 23. Iss. 1. 2020. Article 20.1.2.
• Natalia Makarova, All 67 rules for SN DLS of order 11
• Natalia Makarova and Harry White, About unique diagonals for SN DLS of order 14 and 15
• E. I. Vatutin, About the number of strong normalized lines of diagonal Latin squares of orders 1-10 (in Russian).
• E. I. Vatutin, About the number of strong normalized lines of diagonal Latin squares of order 11 (in Russian).
• E. I. Vatutin, About the a(2*t)=a(2*t+1) equality (in Russian).
• E. I. Vatutin, About the number of equivalence classes of X-based filling of diagonals in a diagonal Latin squares of order 12 (in Russian).
• E. I. Vatutin, About the number of equivalence classes of X-based filling of diagonals in a diagonal Latin squares of order 13 (in Russian).
• E. I. Vatutin, A. D. Belyshev, N. N. Nikitina, and M. O. Manzuk, Use of X-based diagonal fillings and ESODLS CMS schemes for enumeration of main classes of diagonal Latin squares, Telecommunications, 2023, No. 1, pp. 2-16, DOI: 10.31044/1684-2588-2023-0-1-2-16 (in Russian).
• Index entries for sequences related to Latin squares and rectangles.

Crossrefs

Cf. A274171, A274806, A337302, A338084.

Formula

a(n) = A338084(floor(n/2)).

Extensions

a(11) added by Eduard I. Vatutin, Aug 21 2020

a(12)-a(13) by Harry White, added by Natalia Makarova, Sep 12 2020

a(0)=1 prepended by Andrew Howroyd, Oct 31 2020