A091323 -id:A091323 - cp's OEIS frontend

A092237 Maximum number of intercalates in a Latin square of order n.

0, 1, 0, 12, 4, 27, 42, 112, 72

Offset: 1

Richard Bean, Feb 17 2004

An intercalate is a 2 X 2 subsquare of a Latin square. a(10) >= 125, a(11) >= 172, a(12) >= 324.
a(13) >= 208, a(14) >= 391, a(15) >= 630, a(16) >= 960, a(17) >= 736, a(18) >= 729, a(19) >= 472, a(20) >= 1500, a(21) >= 884, a(22) >= 1497, a(23) >= 983, a(24) >= 1872, a(25) >= 1700, a(26) >= 2197, a(27) >= 648, a(28) >= 2940. - Eduard I. Vatutin, Mar 02 2025
If, in theory, all unordered pairs of rows and columns form intercalate in their intersection, total number of intercalates will be (n*(n-1))^2, so a(n) <= (n*(n-1))^2, a(n) is asymptotically less than O(n^4). In practice a(n) << (n*(n-1))^2. - Eduard I. Vatutin, Mar 11 2025
a(2^n-1) = 42*A006096(n) for n > 2. - Eduard I. Vatutin, Apr 23 2025
Due to existence of the pine Latin squares for even orders N=2n, a(2n) >= A383368(n). Pine Latin squares exist for all even orders, so a(N) >= (2k)^2 * (2k + 1) for N=4k and a(N) >= (2k+1)^3 for N=4k+2. Therefore, asymptotically maximum number of intercalates in Latin squares of even orders N greater or equal than o(k1*N^3), where k1 = 1/8. - Eduard I. Vatutin, Apr 30 2025
From Eduard I. Vatutin, Jul 01 2025: (Start)
Table showing minimums and maximums:
  order                      | 1 2 3  4 5  6  7   8   9    10    11    12    13    14    15    16    17    18    19
  min number of intercalates | 0 1 0  4 0  0  0   0   0     0     0     0     0     0     0     0     0     0     0
  max number of intercalates | 0 1 0 12 4 27 42 112  72 >=125 >=172 >=324 >=208 >=391 >=630 >=960 >=736 >=729 >=472 (this sequence)
.
  order                      |      20    21     22    23     24     25     26    27     28 29
  min number of intercalates |       0     0      0     0      0      0   <=15     0    <=1  0
  max number of intercalates |  >=1500 >=884 >=1497 >=983 >=1872 >=1700 >=2197 >=648 >=2940  ? (this sequence)
(End)

I. Wanless, Private communication, 2003.

R. Bean, Critical sets in Latin squares and associated structures, Ph.D. Thesis, The University of Queensland, 2001.
K. Heinrich and W. Wallis, The maximum number of intercalates in a Latin square, Combinatorial Math. VIII, Proc. 8th Australian Conf. Combinatorics, 1980, 221-233.
Eduard I. Vatutin, Proving list, minimum number of intercalates (best known examples).
Eduard I. Vatutin, Proving list, maximum number of intercalates (best known examples).
Eduard I. Vatutin, About interconnection between maximum number of intercalates in Latin squares of order N=2^n-1 and Gaussian binomial coefficients [n,3] for q=2 (in Russian).
Index entries for sequences related to Latin squares and rectangles.

Cf. A006096, A016152, A091323, A090741, A383368.

If n is a power of 2, a(n) = n^2*(n-1)/4 = A016152(log2(n)); if n is one less than a power of 2, a(n) = n*(n-1)*(n-3)/4 = A006096(log2(n+1))*42. - updated by Eduard I. Vatutin, Jun 28 2025

A287645 Minimum number of transversals in a diagonal Latin square of order n.

Original entry on oeis.org

1, 0, 0, 8, 3, 32, 7, 8, 68

Offset: 1

Eduard I. Vatutin, May 29 2017

From Eduard I. Vatutin, Sep 20 2020: (Start)
Every diagonal Latin square is a Latin square, so 0 <= a(n) <= A287644(n) <= A090741(n).
A lower bound for odd n is A091323((n-1)/2) <= a(n). (End)
By definition, the main diagonal and antidiagonal of a diagonal Latin square are transversals, so a(n)>=2 for all n>=4 (the two diagonals are the same in the order 1 square and there are no diagonal Latin squares of orders 2 or 3). - Eduard I. Vatutin, Jun 13 2021
All cyclic diagonal Latin squares are diagonal Latin squares, so a(n) <= A348212((n-1)/2) for all orders n of which cyclic diagonal Latin squares exist. - Eduard I. Vatutin, Mar 25 2021
a(10) <= 128, a(11) <= 814, a(12) <= 448, a(13) <= 43093, a(14) <= 25720, a(15) <= 215721, a(16) <= 7465984. - Eduard I. Vatutin, Mar 11 2021, updated Feb 12 2025

			From _Eduard I. Vatutin_, Apr 24 2021: (Start)
For example, diagonal Latin square
  0 1 2 3
  3 2 1 0
  1 0 3 2
  2 3 0 1
has 4 diagonal transversals (see A287648)
  0 . . .   . 1 . .   . . 2 .   . . . 3
  . . 1 .   . . . 0   3 . . .   . 2 . .
  . . . 2   . . 3 .   . 0 . .   1 . . .
  . 3 . .   2 . . .   . . . 1   . . 0 .
and 4 not diagonal transversals
  0 . . .   . 1 . .   . . 2 .   . . . 3
  . 2 . .   3 . . .   . . . 0   . . 1 .
  . . 3 .   . . . 2   1 . . .   . 0 . .
  . . . 1   . . 0 .   . 3 . .   2 . . .
total 8 transversals. (End)

E. I. Vatutin, Discussion about properties of diagonal Latin squares at forum.boinc.ru (in Russian).
E. I. Vatutin, About the minimal and maximal number of transversals in diagonal Latin squares of order 9 (in Russian).
Eduard I. Vatutin, Best examples presently known.
E. I. Vatutin, S. E. Kochemazov, and O. S. Zaikin, Estimating of combinatorial characteristics for diagonal Latin squares, Recognition — 2017 (2017), pp. 98-100 (in Russian)
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, S. E. Kochemazov, O. S. Zaikin, and S. Yu. Valyaev, Using Volunteer Computing to Study Some Features of Diagonal Latin Squares. Open Engineering. Vol. 7. Iss. 1. 2017. pp. 453-460. DOI: 10.1515/eng-2017-0052
E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev, and V. S. Titov, Estimating the Number of Transversals for Diagonal Latin Squares of Small Order, Telecommunications. 2018. No. 1. pp. 12-21 (in Russian).
Eduard I. Vatutin, Natalia N. Nikitina, and Maxim O. Manzuk, First results of an experiment on studying the properties of DLS of order 9 in the volunteer distributed computing projects Gerasim@Home and RakeSearch (in Russian).
E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, I. I. Kurochkin, A. M. Albertyan, On the number of transversals in diagonal Latin squares of even orders (in Russian), Cloud and distributed computing systems, within the National supercomputing forum (NSCF - 2023). Pereslavl-Zalessky, 2023. pp. 101-105.
E. Vatutin, A. Belyshev, N. Nikitina, and M. Manzuk, Evaluation of Efficiency of Using Simple Transformations When Searching for Orthogonal Diagonal Latin Squares of Order 10, Communications in Computer and Information Science, Vol. 1304, Springer, 2020, pp. 127-146, DOI: 10.1007/978-3-030-66895-2_9.
E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, A. M. Albertyan and I. I. Kurochkin, On the construction of spectra of fast-computable numerical characteristics for diagonal Latin squares of small order, Intellectual and Information Systems (Intellect - 2021). Tula, 2021. pp. 7-17. (in Russian)
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)
E. I. Vatutin, V. S. Titov, A. I. Pykhtin, A. V. Kripachev, N. N. Nikitina, M. O. Manzuk, A. M. Albertyan and I. I. Kurochkin, Estimation of the Cardinalities of the Spectra of Fast-computable Numerical Characteristics for Diagonal Latin Squares of Orders N>9 (in Russian) // Science and education in the development of industrial, social and economic spheres of Russian regions. Murom, 2022. pp. 314-315.
Index entries for sequences related to Latin squares and rectangles.

Cf. A091323, A287644, A287647, A287648, A344105.

a(8) added by Eduard I. Vatutin, Oct 29 2017

a(9) added by Eduard I. Vatutin, Sep 20 2020

A309344 a(n) is the number of distinct numbers of transversals of order n Latin squares.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 36, 74

Offset: 1

Alvaro R. Belmonte, Eugene Fiorini, Peterson Lenard, Froylan Maldonado, Sabrina Traver, Wing Hong Tony Wong, Jul 24 2019

We found all transversals in the main class Latin square representatives of order n.
These results are based upon work supported by the National Science Foundation under the grants numbered DMS-1852378 and DMS-1560019.
For all spectra of even orders all known values included in them are divisible by 2. For all spectra of orders n=4k+2 all known values included in the corresponding spectra are divisible by 4. - Eduard I. Vatutin, Mar 01 2025
a(9)>=407, a(10)>=463, a(11)>=6437, a(12)>=23715. - Eduard I. Vatutin, added Mar 01 2025, updated Aug 14 2025

			For n=7, the number of transversals that an order 7 Latin square may have is 3, 7, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 37, 41, 43, 45, 47, 55, 63, or 133. Hence there are 36 distinct numbers of transversals of order 7 Latin squares, so a(7)=36.

Brendan McKay, Combinatorial Data.
Eduard I. Vatutin, Graphical representation of the spectra.
Eduard I. Vatutin, Proving lists (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12).
E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, I. I. Kurochkin, A. M. Albertyan, On the number of transversals in diagonal Latin squares of even orders (in Russian), Cloud and distributed computing systems, within the National supercomputing forum (NSCF - 2023). Pereslavl-Zalessky, 2023. pp. 101-105.
Index entries for sequences related to Latin squares and rectangles.

Cf. A003090, A090741 (maximum number), A091323 (minimum number), A301371, A308853, A309088, A344105 (version for diagonal Latin squares).

%This extracts entries from each column.  For an example, if
%A=[1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16], and if list = (2, 1, 4),
%this code extracts the second element in the first column, the first
%element in the second column, and the fourth element in the third column.
function [output] = extract(matrix,list)
for i=1:length(list)
    output(i) = matrix(list(i),i);
end
end
%Searches matrix to find transversal and outputs the transversal.
function [output] = findtransversal(matrix)
n=length(matrix);
for i=1:n
    partialtransversal(i,1)=i;
end
for i=2:n
    newpartialtransversal=[];
    for j=1:length(partialtransversal)
        for k=1:n
            if (~ismember(k,partialtransversal(j,:)))&(~ismember(matrix(k,i),extract(matrix,partialtransversal(j,:))))
                newpartialtransversal=[newpartialtransversal;[partialtransversal(j,:),k]];
            end
        end
    end
    partialtransversal=newpartialtransversal;
end
output=partialtransversal;
end
%Takes input of n^2 numbers with no spaces between them and converts it
%into an n by n matrix.
function [A] = tomatrix(input)
n=sqrt(floor(log10(input))+2);
for i=1:n^2
    temp(i)=mod(floor(input/(10^(i-1))),10);
end
for i=1:n
    for j=1:n
        A(i,j)=temp(n^2+1-(n*(i-1)+j));
    end
end
A=A+ones(n);
end

A383684 Minimum number of transversals in an extended self-orthogonal diagonal Latin square of order n.

Original entry on oeis.org

1, 0, 0, 8, 15, 0, 23, 128, 133, 716

Offset: 1

Eduard I. Vatutin, May 05 2025

A self-orthogonal diagonal Latin square (SODLS) is a diagonal Latin square orthogonal to its transpose. An extended self-orthogonal diagonal Latin square (ESODLS) is a diagonal Latin square that has an orthogonal diagonal Latin square from the same main class. SODLS is a special case of ESODLS.

Eduard I. Vatutin, About the properties of ESODLS of orders 1-10 (in Russian).
Eduard I. Vatutin, Proving list (best known examples).
Index entries for sequences related to Latin squares and rectangles.

Cf. A090741, A091323, A287644, A287645, A309210, A309598, A309599, A357514, A387124, A387187.

A387124 Maximum number of transversals in an extended self-orthogonal diagonal Latin square of order n.

Original entry on oeis.org

1, 0, 0, 8, 15, 0, 133, 384, 2241, 988

Offset: 1

Eduard I. Vatutin, Aug 17 2025

Eduard I. Vatutin, About the properties of ESODLS of orders 1-10 (in Russian).
Eduard I. Vatutin, Proving list (best known examples).
Index entries for sequences related to Latin squares and rectangles.

Cf. A090741, A091323, A287644, A287645, A309210, A309598, A309599, A357514, A383684, A387187.

A383570 Number of transversals in pine Latin squares of order 4n.

Original entry on oeis.org

8, 384, 76032, 62881792

Offset: 1

Eduard I. Vatutin, Apr 30 2025

A pine Latin square is a not necessarily canonical composite Latin square of order N=2*K formed from specially arranged cyclic Latin squares of order K.
By construction, pine Latin square is determined one-to-one by the cyclic square used, so number of pine Latin squares of order N is equal to number of cyclic Latin squares of order N/2.
All pine Latin squares are horizontally symmetric column-inverse Latin squares.
All pine Latin squares for selected order N are isomorphic one to another as Latin squares, so they have same properties (number of transversals, intercalates, etc.).
Pine Latin squares have interesting properties, for example, maximum known number of intercalates (see A383368 and A092237) for some orders N (at least N in {2, 4, 6, 10, 18}).
Pine Latin squares do not exist for odd orders because they must be horizontally symmetric.
Hypothesis: number of transversals in pine Latin squares of all orders N=4k+2 is zero (verified for orders N<=18).

			For order N=8 pine Latin square
  0 1 2 3 4 5 6 7
  1 2 3 0 7 4 5 6
  2 3 0 1 6 7 4 5
  3 0 1 2 5 6 7 4
  4 5 6 7 0 1 2 3
  5 6 7 4 3 0 1 2
  6 7 4 5 2 3 0 1
  7 4 5 6 1 2 3 0
has 384 transversals.
.
For order N=10 pine Latin square
  0 1 2 3 4 5 6 7 8 9
  1 2 3 4 0 9 5 6 7 8
  2 3 4 0 1 8 9 5 6 7
  3 4 0 1 2 7 8 9 5 6
  4 0 1 2 3 6 7 8 9 5
  5 6 7 8 9 0 1 2 3 4
  6 7 8 9 5 4 0 1 2 3
  7 8 9 5 6 3 4 0 1 2
  8 9 5 6 7 2 3 4 0 1
  9 5 6 7 8 1 2 3 4 0
has no transversals.
.
For order N=12 pine Latin square
  0 1 2 3 4 5 6 7 8 9 10 11
  1 2 3 4 5 0 11 6 7 8 9 10
  2 3 4 5 0 1 10 11 6 7 8 9
  3 4 5 0 1 2 9 10 11 6 7 8
  4 5 0 1 2 3 8 9 10 11 6 7
  5 0 1 2 3 4 7 8 9 10 11 6
  6 7 8 9 10 11 0 1 2 3 4 5
  7 8 9 10 11 6 5 0 1 2 3 4
  8 9 10 11 6 7 4 5 0 1 2 3
  9 10 11 6 7 8 3 4 5 0 1 2
  10 11 6 7 8 9 2 3 4 5 0 1
  11 6 7 8 9 10 1 2 3 4 5 0
has 76032 transversals.

Richard Bean, Critical sets in Latin squares and associated structures, Ph.D. Thesis, The University of Queensland, 2001.
Eduard I. Vatutin, About the properties of pine Latin squares (in Russian).
Eduard I. Vatutin, Proving list (examples).
Index entries for sequences related to Latin squares and rectangles.

Cf. A002860, A091323, A090741, A338522, A383368.

A336764 Maximum number of order 3 subsquares in a Latin square of order n.

Original entry on oeis.org

0, 0, 1, 0, 0, 4, 7

Offset: 1

Omar Aceval Garcia, Cameron Byer, Eugene Fiorini, Nicholas Hanson, Brian G. Kronenthal, Lindsey Wise, Aug 03 2020

A subsquare of a Latin square is a submatrix (not necessarily consisting of adjacent entries) which is itself a Latin square. (I. M. Wanless, Latin Squares with One Subsquare, Wiley and Sons)

R. Bean, Critical sets in Latin squares and Associated Structures, Ph.D. Thesis, The University of Queensland, 2001.
K. Heinrich and W. Wallis, The Maximum Number of Intercalates in a Latin Square, Combinatorial Math. VIII, Proc. 8th Australian Conf. Combinatorics, 1980, 221-233.
I. M. Wanless, Latin Squares with One Subsquare, Journal of Combinatorial Designs, 9 (2001), 128-146.

Cf. A092237, A091323, A090741, A307163, A307164.

a(3^n) = 9*a(3^(n-1)) + 27^(n-1) (conjectured).

cp's OEIS Frontend

A092237 Maximum number of intercalates in a Latin square of order n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A287645 Minimum number of transversals in a diagonal Latin square of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A309344 a(n) is the number of distinct numbers of transversals of order n Latin squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

A383684 Minimum number of transversals in an extended self-orthogonal diagonal Latin square of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

A387124 Maximum number of transversals in an extended self-orthogonal diagonal Latin square of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

A383570 Number of transversals in pine Latin squares of order 4n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A336764 Maximum number of order 3 subsquares in a Latin square of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula