cp's OEIS Frontend

A264041 a(n) is the maximum number of diagonals that can be placed in an n X n grid made up of 1 X 1 unit squares when diagonals are placed in the unit squares in such a way that no two diagonals may cross or intersect at an endpoint.

%I A264041 #173 Aug 12 2025 20:31:09
%S A264041 1,3,6,10,16,21,29,36,46,55,68,78,93,105,122,136,156,171,193,210,234,
%T A264041 253,280,300,329,351,382,406,440,465,501,528
%N A264041 a(n) is the maximum number of diagonals that can be placed in an n X n grid made up of 1 X 1 unit squares when diagonals are placed in the unit squares in such a way that no two diagonals may cross or intersect at an endpoint.
%C A264041 In other words, largest number of nonintersecting vertex-disjoint diagonals / and \ that can be packed in an n X n grid.
%C A264041 / and \ cannot be adjacent horizontally or vertically.
%C A264041 Two \ cannot be adjacent on a northwest-to-southeast diagonal, two / cannot be adjacent on a southwest-to-northeast diagonal.
%C A264041 We also extended this to m X n grids, and have some limited results.
%C A264041 a(n) is the size of a maximum independent set in a graph with vertices (x,y,z), x=1..n, y=1..n, z=1..2, with edges joining (x,y,z) to (x,y,3-z), (x+1,y,3-z), and (x,y+1,3-z), (x,y,1) to (x+1,y-1,1) and (x,y,2) to (x+1,y+1,2). - _Robert Israel_, Nov 01 2015
%C A264041 From _Rob Pratt_, Nov 09 2015: (Start)
%C A264041 382 <= a(27) <= 383.
%C A264041 a(29) = 440.
%C A264041 For the number of optimal solutions see A264667. (End)
%C A264041 Conjecture: partial sums of A260307. - _Sean A. Irvine_, Jul 15 2022
%C A264041 From _Aleksandr V. Novozhilov_, Apr 01 2025: (Start)
%C A264041 a(27) = 382.
%C A264041 a(31) = 501.
%C A264041 566 <= a(33) <= 567.
%C A264041 636 <= a(35) <= 637. (End)
%C A264041 a(35) = 636, proved using SCIP ILP solver. - _Aleksandr V. Novozhilov_, Apr 09 2025
%H A264041 Peter Boyland, Gabriella Pintér, István Laukó, Ivan Roth, Jon E. Schoenfield, and Stephen Wasielewski, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Pinter/pinter3.html">On the Maximum Number of Non-intersecting Diagonals in an Array</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.4.
%H A264041 Robert Israel, <a href="/A264041/a264041.m.txt">Code for MATLAB with CPLEX</a>
%H A264041 Robert Israel, <a href="/A264041/a264041_1.pdf">Optimal configurations for n=1..26</a>
%H A264041 Mathematics StackExchange, <a href="http://math.stackexchange.com/questions/339387/">How to solve 5x5 grid with 16 diagonals</a>
%H A264041 Aleksandr V. Novozhilov, <a href="/A264041/a264041_3.pdf">Optimal configurations for n=1..32</a>
%H A264041 NRICH, <a href="http://nrich.maths.org/6784">Distinct Diagonals</a>
%H A264041 Gabriella Pinter, <a href="/A264041/a264041_1.jpg">Figure used to illustrate proof of lower bound in n=6k-1 case, k=1,2,3</a>
%H A264041 Gabriella Pinter, <a href="/A264041/a264041_1.txt">Lower bound for the case n = 6k-1</a>, Oct 27 2015
%H A264041 Gabriella Pinter, <a href="/A264041/a264041_3.txt">Solution when there are an even number of rows of cells</a>
%H A264041 Yaohui Zhu, Kaiming Sun, Zhengdong Luo, and Lingfeng Wang, <a href="https://doi.org/10.1609/aaai.v39i2.32162">Progressive Self-Learning for Domain Adaptation on Symbolic Regression of Integer Sequences</a>, Proc. 39th AAAI Conf. Artif. Intel. (2025) Vol. 39, No. 1, 1692-1699. See p. 1698.
%F A264041 Theorem: a(2*n) = n*(2n+1) (the even-indexed terms among the triangular numbers A000217). More generally, for the 2k X m case, the optimal solution is k*(m+1). See third Pinter link for proof.
%F A264041 Theorem: a(6*n-1) >= n + 3*n*(6*n-1). See second Pinter link for proof.
%F A264041 Theorem: a(n) <= a(n-2) + 2*n.
%F A264041 Empirical g.f.: x*(1 + 2*x + 2*x^2 + 2*x^3 + 3*x^4 + x^5 + x^6) / ((1 - x)^3*(1 + x)^2*(1 - x + x^2)*(1 + x + x^2)). - _Robert Israel_, Nov 01 2015. Corrected by _Colin Barker_, Jan 31 2018
%F A264041 a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9) for n>9 (conjectured). - _Colin Barker_, Jan 31 2018
%F A264041 a(n) = n*(n+1)/2 for n even, floor(n*(n/2+2/3)+1/6) for n odd (conjecture). - _Bill McEachen_, Aug 11 2025
%e A264041 For a(2) = 3, an optimal configuration is
%e A264041    //
%e A264041    ./
%e A264041 (This is best seen using a fixed-width font. It is better to use "." instead of " " for blank squares, because " " tends to disappear.)
%e A264041 Note that the bottom left square can't have / because that would conflict with the / at top right, or \ because that would conflict with its horizontal and vertical neighbors.
%e A264041 For a(3) = 6, an optimal configuration is
%e A264041    ///
%e A264041    ../
%e A264041    /./
%e A264041 For a(4) = 10, an optimal configuration may be depicted, with the grid lines explicitly drawn, as
%e A264041    +-+-+-+-+
%e A264041    |/| |\|\|
%e A264041    +-+-+-+-+
%e A264041    |/| |\| |
%e A264041    +-+-+-+-+
%e A264041    |/| | | |
%e A264041    +-+-+-+-+
%e A264041    |/|/|/|/|
%e A264041    +-+-+-+-+
%e A264041 or, using "o" and "." to represent used and unused vertices, as
%e A264041    .-o-o-o-.
%e A264041    |/| |\|\|
%e A264041    o-o-o-o-o
%e A264041    |/| |\| |
%e A264041    o-o-.-o-.
%e A264041    |/| | | |
%e A264041    o-o-o-o-o
%e A264041    |/|/|/|/|
%e A264041    o-o-o-o-.
%e A264041 For a(5) = 16, an optimal configuration is
%e A264041    ///.\
%e A264041    ../.\
%e A264041    \\.\\
%e A264041    \./..
%e A264041    \.///
%e A264041 For more examples, see the link "Optimal configurations for n=1..32".
%Y A264041 Cf. A000217 (triangular numbers), A260708 (the same?), A264938 (first bisection?), A264667.
%Y A264041 Cf. A299017 (intersection with A000217).
%K A264041 nonn,more,nice
%O A264041 1,2
%A A264041 _Gabriella Pinter_, Stephen Wasielewski, Peter Boyland, Ivan Roth, G. Christopher Hruska, Jeb Willenbring, Oct 22 2015
%E A264041 Additional comments and terms a(9)-a(26) from _Robert Israel_, Nov 01 2015
%E A264041 This entry is the result of merging two independent submissions, merged by _N. J. A. Sloane_, Nov 11 2015
%E A264041 Cases n=27, n=31 proved using SCIP ILP solver by _Aleksandr V. Novozhilov_, Apr 01 2025