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.

1, 3, 6, 10, 16, 21, 29, 36, 46, 55, 68, 78, 93, 105, 122, 136, 156, 171, 193, 210, 234, 253, 280, 300, 329, 351, 382, 406, 440, 465, 501, 528

Offset: 1

Author

Gabriella Pinter, Stephen Wasielewski, Peter Boyland, Ivan Roth, G. Christopher Hruska, Jeb Willenbring, Oct 22 2015

Keywords

• nonn
• more
• nice

Comments

In other words, largest number of nonintersecting vertex-disjoint diagonals / and \ that can be packed in an n X n grid.

/ and \ cannot be adjacent horizontally or vertically.

Two \ cannot be adjacent on a northwest-to-southeast diagonal, two / cannot be adjacent on a southwest-to-northeast diagonal.

We also extended this to m X n grids, and have some limited results.

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

From Rob Pratt, Nov 09 2015: (Start)

382 <= a(27) <= 383.

a(29) = 440.

For the number of optimal solutions see A264667. (End)

Conjecture: partial sums of A260307. - Sean A. Irvine, Jul 15 2022

From Aleksandr V. Novozhilov, Apr 01 2025: (Start)

a(27) = 382.

a(31) = 501.

566 <= a(33) <= 567.

636 <= a(35) <= 637. (End)

a(35) = 636, proved using SCIP ILP solver. - Aleksandr V. Novozhilov, Apr 09 2025

Examples

			For a(2) = 3, an optimal configuration is
   //
   ./
(This is best seen using a fixed-width font. It is better to use "." instead of " " for blank squares, because " " tends to disappear.)
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.
For a(3) = 6, an optimal configuration is
   ///
   ../
   /./
For a(4) = 10, an optimal configuration may be depicted, with the grid lines explicitly drawn, as
   +-+-+-+-+
   |/| |\|\|
   +-+-+-+-+
   |/| |\| |
   +-+-+-+-+
   |/| | | |
   +-+-+-+-+
   |/|/|/|/|
   +-+-+-+-+
or, using "o" and "." to represent used and unused vertices, as
   .-o-o-o-.
   |/| |\|\|
   o-o-o-o-o
   |/| |\| |
   o-o-.-o-.
   |/| | | |
   o-o-o-o-o
   |/|/|/|/|
   o-o-o-o-.
For a(5) = 16, an optimal configuration is
   ///.\
   ../.\
   \\.\\
   \./..
   \.///
For more examples, see the link "Optimal configurations for n=1..32".
		

Links

• Peter Boyland, Gabriella Pintér, István Laukó, Ivan Roth, Jon E. Schoenfield, and Stephen Wasielewski, On the Maximum Number of Non-intersecting Diagonals in an Array, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.4.
• Robert Israel, Code for MATLAB with CPLEX
• Robert Israel, Optimal configurations for n=1..26
• Mathematics StackExchange, How to solve 5x5 grid with 16 diagonals
• Aleksandr V. Novozhilov, Optimal configurations for n=1..32
• NRICH, Distinct Diagonals
• Gabriella Pinter, Figure used to illustrate proof of lower bound in n=6k-1 case, k=1,2,3
• Gabriella Pinter, Lower bound for the case n = 6k-1, Oct 27 2015
• Gabriella Pinter, Solution when there are an even number of rows of cells
• Yaohui Zhu, Kaiming Sun, Zhengdong Luo, and Lingfeng Wang, Progressive Self-Learning for Domain Adaptation on Symbolic Regression of Integer Sequences, Proc. 39th AAAI Conf. Artif. Intel. (2025) Vol. 39, No. 1, 1692-1699. See p. 1698.

Crossrefs

Cf. A000217 (triangular numbers), A260708 (the same?), A264938 (first bisection?), A264667.

Cf. A299017 (intersection with A000217).

Formula

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.

Theorem: a(6*n-1) >= n + 3*n*(6*n-1). See second Pinter link for proof.

Theorem: a(n) <= a(n-2) + 2*n.

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

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

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

Extensions

Additional comments and terms a(9)-a(26) from Robert Israel, Nov 01 2015

This entry is the result of merging two independent submissions, merged by N. J. A. Sloane, Nov 11 2015

Cases n=27, n=31 proved using SCIP ILP solver by Aleksandr V. Novozhilov, Apr 01 2025