|
|
A287647
|
|
Minimum number of diagonal transversals in a diagonal Latin square of order n.
|
|
9
|
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
A diagonal Latin square is a Latin square in which both the main diagonal and main antidiagonal contain each element.
A diagonal transversal is a transversal that includes exactly one element from the main diagonal and exactly one from the antidiagonal. For squares of odd orders, these elements can coincide at the intersection of the diagonals.
All cyclic diagonal Latin squares (see A338562) are diagonal Latin squares, so a(n) <= A342998((n-1)/2). (End)
a(10) <= 3, a(11) <= 145, a(12) = 0, a(13) <= 4756, a(14) <= 5173, a(15) <= 15510, a(16) <= 898988, a(17) <= 12058840, a(18) <= 82577875, a(19) <= 592174879, a(20) <= 4488686380. - Eduard I. Vatutin, Sep 26 2021, updated Jul 10 2023
|
|
LINKS
|
E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin and S. Yu. Valyaev, Enumerating the Transversals for Diagonal Latin Squares of Small Order. CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6-14. urn:nbn:de:0074-1973-0.
E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, I. I. Kurochkin, A. M. Albertyan, A. V. Kripachev, and A. I. Pykhtin, Methods for getting spectra of fast computable numerical characteristics of diagonal Latin squares, Cloud and distributed computing systems in electronic control conference, within the National supercomputing forum (NSCF - 2022). Pereslavl-Zalessky, 2023. pp. 19-23. (in Russian)
|
|
EXAMPLE
|
For example, the diagonal Latin square
0 1 2 3
3 2 1 0
1 0 3 2
2 3 0 1
has 4 diagonal transversals:
0 . . . . 1 . . . . 2 . . . . 3
. . 1 . . . . 0 3 . . . . 2 . .
. . . 2 . . 3 . . 0 . . 1 . . .
. 3 . . 2 . . . . . . 1 . . 0 .
In addition there are 4 other transversals that are not diagonal transversals and are therefore not included here. (End)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|