Richard Bean - cp's OEIS frontend

A356650 Domination number of the Cartesian product of four n-cycles.

Original entry on oeis.org

1, 4, 9, 32

Offset: 1

Richard Bean, Aug 20 2022

76 <= a(5) <= 84.

Cf. A094087.

a(9*n) = 729*n^4.

A356649 Domination number of the Cartesian product of three n-cycles.

Original entry on oeis.org

1, 2, 5, 12, 20, 36, 49

Offset: 1

Richard Bean, Aug 19 2022

80 <= a(8) <= 88, 110 <= a(9) <= 122, 147 <= a(10) <= 174, 194 <= a(11) <= 236, 249 <= a(12) <= 303, 316 <= a(13) <= 372.

Cf. A094087.

a(7*n) = 49*n^3.

A091323 Minimum number of transversals in a Latin square of order 2n+1.

Original entry on oeis.org

1, 3, 3, 3, 68

Offset: 0

Richard Bean, Feb 17 2004

Ryser conjectured that a(n) >= 1 for all n. For even orders the number is 0, since the group table for Z_2n has no transversals.

a(5)<=814, a(6)<=43093, a(7)<=215721. - Eduard I. Vatutin, added Apr 09 2024, updated Jan 13 2025

H. J. Ryser, Neuere Probleme der Kombinatorik. Vortraege ueber Kombinatorik, Oberwolfach, 1967, Mathematisches Forschungsinstitut Oberwolfach, pp. 69-91.

B. D. McKay, J. C. McLeod and I. M. Wanless, The number of transversals in a Latin square, Des. Codes Cryptogr., 40, (2006) 269-284.
V. N. Potapov, On the number of transversals in Latin squares, arxiv:1506.01577 [math.CO], 2015.
Eduard I. Vatutin, Proving list (best known examples).
Index entries for sequences related to Latin squares and rectangles.

Cf. A090741, A092237.

a(4) from Brendan McKay and Ian Wanless, May 23 2004

A094087 Domination number of the Cartesian product of two n-cycles.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 12, 16, 18, 20, 27, 32, 38, 42, 45, 56, 64, 71, 76, 80, 95, 104, 114, 120, 125, 144, 155

Offset: 1

Richard Bean, May 01 2004

1/5 <= a(n)/n^2 <= 1/4 for n >= 4; it is conjectured that a(5n-1) = 5*n^2 - n and a(5n+1) = 5n^2 + 4n - 1 for n >= 1. - Richard Bean, Sep 08 2006 [Assadian proves that the both conjectured formulas give the upper bounds. - Andrey Zabolotskiy, Dec 23 2019]

The Cartesian product of two cycles is also called the torus grid graph. - Andrew Howroyd, Feb 29 2020

Navid Assadian, Dominating Sets of the Cartesian Products of Cycles, M. Sc. project, University of Victoria, 2019.
S. Klavžar and N. Seifter, Dominating Cartesian products of cycles, Discrete Applied Mathematics, Vol. 59 (1995), no. 2, pp. 129-136.
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], 2024. See p. 15.
Zehui Shao, Jin Xu, S. M. Sheikholeslami, and Shaohui Wang, The Domination Complexity and Related Extremal Values of Large 3D Torus, Complexity, 2018, 3041426.
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Torus Grid Graph

Cf. A295428, A302406, A303334.

a(5n) = 5n^2. - Richard Bean, Jun 08 2006

More terms from Richard Bean, Sep 08 2006
a(22) from Richard Bean, Jul 24 2018
a(23)-a(24) from Shao et al. added by Andrey Zabolotskiy, Dec 23 2019
a(25)-a(27) from Richard Bean, Apr 03 2022

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

Original entry on oeis.org

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

A090741 Maximum number of transversals in a Latin square of order n.

Original entry on oeis.org

1, 0, 3, 8, 15, 32, 133, 384, 2241

Offset: 1

Richard Bean, Feb 03 2004

a(10) >= 5504 from Parker.

a(n) >= the number of transversals in a cyclic Latin square of the same order which for odd n is given by A006717((n-1)/2). - Eduard I. Vatutin, Nov 04 2020

			a(1), a(3), a(5), a(7) are from the group tables for Z_1, Z_3, Z_5 and Z_7 (see sequence A006717); a(4) and a(8) are from Z_2 x Z_2 and the non-cyclic groups of order 8 (see Bedford).
a(9) = 2241 from Z_3 x Z_3.

J. W. Brown, F. Cherry, L. Most, M. Most, E. T. Parker, W. D. Wallis, Completion of the spectrum of orthogonal diagonal Latin squares, Lecture notes in pure and applied mathematics. 1992. Vol. 139. pp. 43-49.
E. T. Parker, Computer investigations of orthogonal Latin squares of order 10, Proc. Sympos. Appl. Math., volume 15 (1963), 73-81.

D. Bedford, Transversals in the Cayley tables of the non-cyclic groups of order 8, European Journal of Combinatorics, volume 12 (1991), 455-458.
N. J. Cavenagh and I. M. Wanless, On the number of transversals in Cayley tables of cyclic groups, Disc. Appl. Math. 158 (2010), 136-146.
B. D. McKay, J. C. McLeod and I. M. Wanless, The number of transversals in a Latin square, Des. Codes Cryptogr., 40, (2006) 269-284.
V. N. Potapov, On the number of transversals in Latin squares, arxiv:1506.01577 [math.CO], 2015.
Eduard Vatutin, Alexey Belyshev, Natalia Nikitina, Maxim Manzuk, Alexander Albertian, Ilya Kurochkin, Alexander Kripachev, and Alexey Pykhtin, Diagonalization and Canonization of Latin Squares, Supercomputing, Russian Supercomputing Days (RuSCDays 2023) Rev. Selected Papers Part II, LCNS Vol. 14389, Springer, Cham, 48-61.
Ian M. Wanless, A Generalization of Transversals for Latin Squares, Electronic Journal of Combinatorics, volume 9, number 1 (2002), R12.
Index entries for sequences related to Latin squares and rectangles

Cf. A006717, A091325.

a(n) is asymptotically in between 3.2^n and 0.62^n n!. [McKay, McLeod, Wanless], [Cavenagh, Wanless]. - Ian Wanless, Jul 30 2010

a(9) = 2241 from Brendan McKay and Ian Wanless, May 23 2004

A083276 Number of distinct chess positions after n plies including differences due to availability and possibility of castling and en passant captures.

Original entry on oeis.org

1, 20, 400, 5362, 72078, 822518, 9417681, 96400068, 988187354, 9183421888, 85375278064, 726155461002

Offset: 0

Richard Bean, Jun 02 2003

This differs from A057745 at 6 ply and above because where an en passant capture would be illegal, the position is essentially the same as where an en passant capture is not available. It is two less than A057745 at 6 ply because the positions after 1. f4 e6/e5 2. Kf2 Qf6 3. f5 g5 are considered to be the same as after 1. f4 g5 2. Kf2 e6/e5 3. f5 Qf6.
Definition: position = position with castling and en passant information, diagram = position without castling and en passant information.
The sequence became finite on Jul 01 2014 with the introduction of a new draw rule which is automatic (the 75-move rule). - François Labelle, Apr 02 2015

Paul Byrne, Confirmation of a(10).
Tim Krabbe's chess blog, Item 283 [Mentions schachzahl1b_e.html]
F. Labelle, Statistics on chess positions
P. Österlund, Computation of a(11).
Reinhard Scharnagl, Schach und Zahlen [a serious approximation to the number of possible chess positions is 2.28*10^46.]
Index entries for sequences related to number of chess games

Cf. A019319, A048987, A057745, A089957.

a(9) from Paul Byrne, Jan 26 2004
a(10) from Arkadiusz Wesolowski, Jan 04 2012
a(11) from Peter Österlund on Feb 22 2013, verified by François Labelle on Jan 08 2017

A080572 Number of ordered pairs (i,j), 0 <= i,j < n, for which (i & j) is nonzero, where & is the bitwise AND operator.

Original entry on oeis.org

0, 0, 1, 2, 7, 8, 15, 24, 37, 38, 49, 62, 81, 98, 121, 146, 175, 176, 195, 216, 247, 272, 307, 344, 387, 420, 463, 508, 559, 608, 663, 720, 781, 782, 817, 854, 909, 950, 1009, 1070, 1141, 1190, 1257, 1326, 1405, 1478, 1561, 1646, 1737, 1802, 1885, 1970, 2065, 2154

Offset: 0

Richard Bean, Feb 22 2003

Conjectured to be less than or equal to lcs(n) (see sequence A063437). The value of a(2^n) is that given in Stinson and van Rees and the value of a(2^n-1) is that given in Fu, Fu and Liao. This function gives an easy way to generate these two constructions.
From Gus Wiseman, Mar 30 2019: (Start)
Also the number of ordered pairs of positive integers up to n with at least one binary carry. A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. For example, the a(2) = 1 through a(6) = 15 ordered pairs are:
  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)
         (2,2)  (1,3)  (1,3)  (1,3)
                (2,2)  (2,2)  (1,5)
                (2,3)  (2,3)  (2,2)
                (3,1)  (3,1)  (2,3)
                (3,2)  (3,2)  (3,1)
                (3,3)  (3,3)  (3,2)
                       (4,4)  (3,3)
                              (3,5)
                              (4,4)
                              (4,5)
                              (5,1)
                              (5,3)
                              (5,4)
                              (5,5)
(End)
a(n) is also the number of even elements in the n X n symmetric Pascal matrix. - Stefano Spezia, Nov 14 2022

C. Fu, H. Fu and W. Liao, A new construction for a critical set in special Latin squares, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, Florida, 1995), Congressus Numerantium, Vol. 110 (1995), pp. 161-166.
D. R. Stinson and G. H. J. van Rees, Some large critical sets, Proceedings of the Eleventh Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, Manitoba, 1981), Congressus Numerantium, Vol. 34 (1982), pp. 441-456.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
R. Bean, Three problems on partial Latin squares, Problem 418 (BCC19,2), Discrete Math., 293 (2005), 314-315.
J. M. Dover, On two OEIS conjectures, arXiv:1606.08033 [math.CO], 2016.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 29.

Cf. A063437.
Cf. A000120, A005061, A006218, A050315, A155609, A247935, A267610, A267700.
Cf. A325096, A325098, A325102, A325103, A325104, A325106, A325124.

f:=proc(n) option remember; local t;
if n <= 1 then 0
elif (n mod 2) =  0 then 3*f(n/2)+(n/2)^2
else t:=(n-1)/2; f(t)+2*f(t+1)+t^2-1; fi; end;
[seq(f(n),n=0..100)]; # N. J. A. Sloane, Jul 01 2017

a[0] = a[1] = 0; a[n_] := a[n] = If[EvenQ[n], 3*a[n/2] + n^2/4, 2*a[(n-1)/2 + 1] + a[(n-1)/2] + (1/4)*(n-1)^2 - 1];
Array[a, 60, 0] (* Jean-François Alcover, Dec 09 2017, from Dover's formula *)
Table[Length[Select[Tuples[Range[n-1],2],Intersection[Position[Reverse[IntegerDigits[#[[1]],2]],1],Position[Reverse[IntegerDigits[#[[2]],2]],1]]!={}&]],{n,0,20}] (* Gus Wiseman, Mar 30 2019 *)

a(2^n) = 4^n-3^n = A005061(n); a(2^n+1) = 4^n-3^n+1 = A155609(n); a(2^n-1) = 4^n-3^n-2^(n+1)+3.
a(0)=a(1)=0, a(2n) = 3a(n)+n^2, a(2n+1) = a(n)+2a(n+1)+n^2-1. This was proved by Jeremy Dover. - Ralf Stephan, Dec 08 2004
a(n) = (A325104(n) - n)/2. - Gus Wiseman, Mar 30 2019

cp's OEIS Frontend

User: Richard Bean

A356650 Domination number of the Cartesian product of four n-cycles.

Views

Author

Keywords

Comments

Crossrefs

Formula

A356649 Domination number of the Cartesian product of three n-cycles.

Views

Author

Keywords

Comments

Crossrefs

Formula

A091323 Minimum number of transversals in a Latin square of order 2n+1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A094087 Domination number of the Cartesian product of two n-cycles.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A090741 Maximum number of transversals in a Latin square of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A083276 Number of distinct chess positions after n plies including differences due to availability and possibility of castling and en passant captures.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A080572 Number of ordered pairs (i,j), 0 <= i,j < n, for which (i & j) is nonzero, where & is the bitwise AND operator.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula