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

%I #78 Jun 06 2023 08:17:26

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

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

%C 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.

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

%C K2 = K1 * n!,

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

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

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

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

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

%C For all t>0 a(2*t) = a(2*t+1). - _Eduard I. Vatutin_, Aug 21 2020

%C a(14) >= 5225, a(15) >= 5225. - _Natalia Makarova_, Sep 12 2020

%C 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

%H S. Kochemazov, O. Zaikin, E. Vatutin, and A. Belyshev, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Zaikin/zaikin3.html">Enumerating Diagonal Latin Squares of Order Up to 9</a>, Journal of Integer Sequences. Vol. 23. Iss. 1. 2020. Article 20.1.2.

%H Natalia Makarova, <a href="https://boinc.progger.info/odlk/forum_thread.php?id=162&amp;postid=6038">All 67 rules for SN DLS of order 11</a>

%H Natalia Makarova and Harry White, <a href="https://boinc.progger.info/odlk/forum_thread.php?id=162&amp;postid=6345#6345">About unique diagonals for SN DLS of order 14 and 15</a>

%H E. I. Vatutin, <a href="https://vk.com/wall162891802_1280">About the number of strong normalized lines of diagonal Latin squares of orders 1-10</a> (in Russian).

%H E. I. Vatutin, <a href="https://vk.com/wall162891802_1292">About the number of strong normalized lines of diagonal Latin squares of order 11</a> (in Russian).

%H E. I. Vatutin, <a href="https://vk.com/wall162891802_1293">About the a(2*t)=a(2*t+1) equality</a> (in Russian).

%H E. I. Vatutin, <a href="https://vk.com/wall162891802_1349">About the number of equivalence classes of X-based filling of diagonals in a diagonal Latin squares of order 12</a> (in Russian).

%H E. I. Vatutin, <a href="https://vk.com/wall162891802_1356">About the number of equivalence classes of X-based filling of diagonals in a diagonal Latin squares of order 13</a> (in Russian).

%H E. I. Vatutin, A. D. Belyshev, N. N. Nikitina, and M. O. Manzuk, <a href="http://evatutin.narod.ru/evatutin_dls_scf_gen.pdf">Use of X-based diagonal fillings and ESODLS CMS schemes for enumeration of main classes of diagonal Latin squares</a>, Telecommunications, 2023, No. 1, pp. 2-16, DOI: 10.31044/1684-2588-2023-0-1-2-16 (in Russian).

%H <a href="/index/La#Latin">Index entries for sequences related to Latin squares and rectangles</a>.

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

%e For order n=4 there are a(4)=2 equivalence classes. First of them C[1] includes two X-based fillings of diagonals

%e 0..1 0..2

%e .13. .10.

%e .02. .32.

%e 2..3 1..3

%e and second C[2] also includes two X-based fillings of diagonals

%e 0..1 0..2

%e .10. .13.

%e .32. .02.

%e 2..3 1..3

%e 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.

%Y Cf. A274171, A274806, A337302, A338084.

%K nonn,more,hard

%O 0,5

%A _Eduard I. Vatutin_, Jul 06 2020

%E a(11) added by _Eduard I. Vatutin_, Aug 21 2020

%E a(12)-a(13) by Harry White, added by _Natalia Makarova_, Sep 12 2020

%E a(0)=1 prepended by _Andrew Howroyd_, Oct 31 2020