login
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.
8

%I #132 Jul 15 2022 21:48:39

%S 1,3,6,10,16,21,29,36,46,55,68,78,93,105,122,136,156,171,193,210,234,

%T 253,280,300,329,351

%N 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 In other words, largest number of nonintersecting vertex-disjoint diagonals / and \ that can be packed in an n X n grid.

%C / and \ cannot be adjacent horizontally or vertically.

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

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

%C 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 From _Rob Pratt_, Nov 09 2015: (Start)

%C 382 <= a(27) <= 383.

%C a(29) = 440.

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

%C Conjecture: partial sums of A260307. - _Sean A. Irvine_, Jul 15 2022

%H Robert Israel, <a href="/A264041/a264041_1.pdf">Optimal configurations for n=1..26</a>

%H 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 Robert Israel, <a href="/A264041/a264041.m.txt">Code for MATLAB with CPLEX</a>

%H Mathematics StackExchange, <a href="http://math.stackexchange.com/questions/339387/">How to solve 5x5 grid with 16 diagonals</a>

%H NRICH, <a href="http://nrich.maths.org/6784">Distinct Diagonals</a>

%H 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 Gabriella Pinter, <a href="/A264041/a264041_1.txt">Lower bound for the case n = 6k-1</a>, Oct 27 2015

%H Gabriella Pinter, <a href="/A264041/a264041_3.txt">Solution when there are an even number of rows of cells</a>

%F 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 Theorem: a(6*n-1) >= n + 3*n*(6*n-1). See second Pinter link for proof.

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

%F 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 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

%e For a(2) = 3, an optimal configuration is

%e //

%e ./

%e (This is best seen using a fixed-width font. It is better to use "." instead of " " for blank squares, because " " tends to disappear.)

%e 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 For a(3) = 6, an optimal configuration is

%e ///

%e ../

%e /./

%e For a(4) = 10, an optimal configuration may be depicted, with the grid lines explicitly drawn, as

%e +-+-+-+-+

%e |/| |\|\|

%e +-+-+-+-+

%e |/| |\| |

%e +-+-+-+-+

%e |/| | | |

%e +-+-+-+-+

%e |/|/|/|/|

%e +-+-+-+-+

%e or, using "o" and "." to represent used and unused vertices, as

%e .-o-o-o-.

%e |/| |\|\|

%e o-o-o-o-o

%e |/| |\| |

%e o-o-.-o-.

%e |/| | | |

%e o-o-o-o-o

%e |/|/|/|/|

%e o-o-o-o-.

%e For a(5) = 16, an optimal configuration is

%e ///.\

%e ../.\

%e \\.\\

%e \./..

%e \.///

%e For more examples, see the link "Optimal configurations for n=1..26".

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

%Y Cf. A299017 (intersection with A000217).

%K nonn,more,nice

%O 1,2

%A _Gabriella Pinter_, Stephen Wasielewski, Peter Boyland, Ivan Roth, G. Christopher Hruska, Jeb Willenbring, Oct 22 2015

%E Additional comments and terms a(9)-a(26) from _Robert Israel_, Nov 01 2015

%E This entry is the result of merging two independent submissions, merged by _N. J. A. Sloane_, Nov 11 2015