A383368 -id:A383368 - 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

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.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula