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