Gabriella Pinter - cp's OEIS frontend

User: Gabriella Pinter

Gabriella Pinter has authored 2 sequences.

A260690 Array read by antidiagonals: D(w,h) is the maximum number of diagonals that can be placed in a w X h grid made up of 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, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 5, 5, 6, 6, 8, 8, 6, 6, 7, 7, 10, 10, 10, 7, 7, 8, 8, 12, 12, 12, 12, 8, 8, 9, 9, 14, 14, 16, 14, 14, 9, 9, 10, 10, 16, 16, 18, 18, 16, 16, 10, 10, 11, 11, 18, 18, 21, 21, 21, 18, 18, 11, 11, 12, 12, 20, 20, 24, 24, 24, 24, 20, 20, 12, 12

Offset: 1

Gabriella Pinter and Jon E. Schoenfield, Nov 15 2015

In other words, D(w,h) is the largest number of nonintersecting vertex-disjoint diagonals that can be packed in a w X h grid.
For the results for square grids (i.e., w=h), see A264041.
If at least one of the two dimensions is even, then the simple packing using the nested L-shape pattern as described in the third Pinter link at A264041 gives an optimal solution, and formulas for the number of diagonals are given below.
If, however, both dimensions are odd, it may be more difficult to find a way to pack the maximum number of diagonals or to determine what that maximum number D(w,h)is. D(w,h) is known (see Example section) for all odd-odd pairs (w,h) in which at least one dimension is less than 19.
Let L(w,h) be the number of diagonals packed in a w X h grid using the nested L-shape pattern described above, and define K(w,h) as the margin by which the number of diagonals in an optimal solution exceeds the number that would be packed using the nested L-shape pattern; i.e., K(w,h) = D(w,h) - L(w,h). If at least one of the two dimensions is even, then K(w,h) = 0; values of K(w,h) when both w and h are odd are shown in a table in the Example section.
Let B(w,h) be the number of optimal solutions (i.e., distinct configurations of D(w,h) diagonals) for a w X h grid; then known results for odd-odd pairs (w,h) include B(1,1) = 2; B(3,3) = 28; B(5,5) = 2; B(7,7) = 480, B(7,9) = 32; B(9,9) = 433284, B(9,11) = 85328, B(9,13) = 7568, B(9,15) = 256; B(11,11) = 256, ..., B(11,17) = 15813376, B(11,19) = 980224, B(11,21) = 25088. The relative scarcity of optimal solutions at a given dimension pair (w,h) may be seen as indicative of the amount of "slack" available for construction of an optimal solution at that pair; e.g., among cases with w=11, there are relatively few solutions (only 256) at h=11 (a (w,h) combination at which a K(w,h)=2 solution is just barely possible), while solutions at h values where K(w,h)=1 do not exist at all for h>21, are just possible at h=21, and become extremely plentiful as h is decreased from 21 to 13.

			The table begins as follows:
.
  h\w| 1  2  3  4  5  6  7  8  9 10 11 12 13
  ---+--------------------------------------
    1| 1  2  3  4  5  6  7  8  9 10 11 12 13
    2| 2  3  4  5  6  7  8  9 10 11 12 13 14
    3| 3  4  6  8 10 12 14 16 18 20 22 24 26
    4| 4  5  8 10 12 14 16 18 20 22 24 26 28
    5| 5  6 10 12 16 18 21 24 27 30 33 36 39
    6| 6  7 12 14 18 21 24 27 30 33 36 39 42
    7| 7  8 14 16 21 24 29 32 37 40 44 48 52
    8| 8  9 16 18 24 27 32 36 40 44 48 52 56
    9| 9 10 18 20 27 30 37 40 46 50 56 60 66
   10|10 11 20 22 30 33 40 44 50 55 60 65 70
   11|11 12 22 24 33 36 44 48 56 60 68 72 79
   12|12 13 24 26 36 39 48 52 60 65 72 78 84
   13|13 14 26 28 39 42 52 56 66 70 79 84 93
.
If at least one of the dimensions (w,h) is even, the exact value of D(w,h) is given by the appropriate formula in the Formula section. A table consisting of only the terms for which both dimensions are odd begins as follows:
.
  h\w| 1   3   5   7   9  11  13  15  17  19  21  23  25
  ---+--------------------------------------------------
    1| 1   3   5   7   9  11  13  15  17  19  21  23  25
    3| 3   6  10  14  18  22  26  30  34  38  42  46  50
    5| 5  10  16  21  27  33  39  45  51  57  63  69  75
    7| 7  14  21  29  37  44  52  60  68  76  84  92 100
    9| 9  18  27  37  46  56  66  76  85  95 105 115 125
   11|11  22  33  44  56  68  79  91 103 115 127 138 150
   13|13  26  39  52  66  79  93 107 120 134 148 162 176
   15|15  30  45  60  76  91 107 122 138 154 169 185 201
   17|17  34  51  68  85 103 120 138 156 173 191 209 227
   19|19  38  57  76  95 115 134 154 173 193 213 232 252
   21|21  42  63  84 105 127 148 169 191 213 234 256 278
   23|23  46  69  92 115 138 162 185 209 232 256 280 303
   25|25  50  75 100 125 150 176 201 227 252 278 303 329
.
The table below shows (with known 0 values replaced by periods and unknown values left blank, for readability) the differences by which D(w,h) exceeds the number of diagonals resulting from application of the simple nested L-shape pattern referred to above:
.
                 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5
  h\w| 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1
  ---+----------------------------------------------------
    1| . . . . . . . . . . . . . . . . . . . . . . . . . .
    3| . . . . . . . . . . . . . . . . . . . . . . . . . .
    5| . . 1 . . . . . . . . . . . . . . . . . . . . . . .
    7| . . . 1 1 . . . . . . . . . . . . . . . . . . . . .
    9| . . . 1 1 1 1 1 . . . . . . . . . . . . . . . . . .
   11| . . . . 1 2 1 1 1 1 1 . . . . . . . . . . . . . . .
   13| . . . . 1 1 2 2 1 1 1 1 1 1 1 . . . . . . . . . . .
   15| . . . . 1 1 2 2 2 2 1 1 1 1 1 1 1 1 1 . . . . . . .
   17| . . . . . 1 1 2 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 . .
   19| . . . . . 1 1 2 2 3 3 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
   21| . . . . . 1 1 1 2 3 3 3 3 2 2 2 2 2 2
   23| . . . . . . 1 1 2 2 3 4 3 3 3
   25| . . . . . . 1 1 2 2 3 3 4 4
   27| . . . . . . 1 1 1 2 2 3 4
   29| . . . . . . 1 1 1 2 2 3     5
   31| . . . . . . . 1 1 2 2
   33| . . . . . . . 1 1 1 2
   35| . . . . . . . 1 1 1 2
   37| . . . . . . . 1 1 1 2
   39| . . . . . . . . 1 1
   41| . . . . . . . . 1 1
   43| . . . . . . . . 1 1
   45| . . . . . . . . 1 1
   47| . . . . . . . . 1 1
   49| . . . . . . . . . 1
   51| . . . . . . . . . 1

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.

A264041 gives the terms along the main diagonal.

D(n,n) = A264041(n).
If exactly one of the dimensions w and h is even, then D(w,h) = x*(y+1)/2 where x and y are the even and odd dimensions, respectively.
If both dimensions are even, then D(w,h) = (x/2)*(y+1) where x is the smaller dimension.
If both dimensions are odd, it can be shown (see Links) that D(w,h) >= (2*s-1)*t + floor((2*sqrt(s^2-s*t+t^2) - 2*s + t)/3) where s = (max(w,h)+1)/2 and t = (min(w,h)+1)/2.

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.

Original entry on oeis.org

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

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

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

			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".

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.

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

Cf. A299017 (intersection with A000217).

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

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

cp's OEIS Frontend

User: Gabriella Pinter

A260690 Array read by antidiagonals: D(w,h) is the maximum number of diagonals that can be placed in a w X h grid made up of 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula