cp's OEIS Frontend

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.

%I A260690 #35 Jul 08 2019 01:54:37
%S A260690 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,
%T A260690 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,
%U A260690 18,18,21,21,21,18,18,11,11,12,12,20,20,24,24,24,24,20,20,12,12
%N 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.
%C A260690 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.
%C A260690 For the results for square grids (i.e., w=h), see A264041.
%C A260690 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.
%C A260690 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.
%C A260690 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.
%C A260690 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.
%H A260690 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.
%F A260690 D(n,n) = A264041(n).
%F A260690 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.
%F A260690 If both dimensions are even, then D(w,h) = (x/2)*(y+1) where x is the smaller dimension.
%F A260690 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.
%e A260690 The table begins as follows:
%e A260690 .
%e A260690   h\w| 1  2  3  4  5  6  7  8  9 10 11 12 13
%e A260690   ---+--------------------------------------
%e A260690     1| 1  2  3  4  5  6  7  8  9 10 11 12 13
%e A260690     2| 2  3  4  5  6  7  8  9 10 11 12 13 14
%e A260690     3| 3  4  6  8 10 12 14 16 18 20 22 24 26
%e A260690     4| 4  5  8 10 12 14 16 18 20 22 24 26 28
%e A260690     5| 5  6 10 12 16 18 21 24 27 30 33 36 39
%e A260690     6| 6  7 12 14 18 21 24 27 30 33 36 39 42
%e A260690     7| 7  8 14 16 21 24 29 32 37 40 44 48 52
%e A260690     8| 8  9 16 18 24 27 32 36 40 44 48 52 56
%e A260690     9| 9 10 18 20 27 30 37 40 46 50 56 60 66
%e A260690    10|10 11 20 22 30 33 40 44 50 55 60 65 70
%e A260690    11|11 12 22 24 33 36 44 48 56 60 68 72 79
%e A260690    12|12 13 24 26 36 39 48 52 60 65 72 78 84
%e A260690    13|13 14 26 28 39 42 52 56 66 70 79 84 93
%e A260690 .
%e A260690 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:
%e A260690 .
%e A260690   h\w| 1   3   5   7   9  11  13  15  17  19  21  23  25
%e A260690   ---+--------------------------------------------------
%e A260690     1| 1   3   5   7   9  11  13  15  17  19  21  23  25
%e A260690     3| 3   6  10  14  18  22  26  30  34  38  42  46  50
%e A260690     5| 5  10  16  21  27  33  39  45  51  57  63  69  75
%e A260690     7| 7  14  21  29  37  44  52  60  68  76  84  92 100
%e A260690     9| 9  18  27  37  46  56  66  76  85  95 105 115 125
%e A260690    11|11  22  33  44  56  68  79  91 103 115 127 138 150
%e A260690    13|13  26  39  52  66  79  93 107 120 134 148 162 176
%e A260690    15|15  30  45  60  76  91 107 122 138 154 169 185 201
%e A260690    17|17  34  51  68  85 103 120 138 156 173 191 209 227
%e A260690    19|19  38  57  76  95 115 134 154 173 193 213 232 252
%e A260690    21|21  42  63  84 105 127 148 169 191 213 234 256 278
%e A260690    23|23  46  69  92 115 138 162 185 209 232 256 280 303
%e A260690    25|25  50  75 100 125 150 176 201 227 252 278 303 329
%e A260690 .
%e A260690 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:
%e A260690 .
%e A260690                  1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5
%e A260690   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
%e A260690   ---+----------------------------------------------------
%e A260690     1| . . . . . . . . . . . . . . . . . . . . . . . . . .
%e A260690     3| . . . . . . . . . . . . . . . . . . . . . . . . . .
%e A260690     5| . . 1 . . . . . . . . . . . . . . . . . . . . . . .
%e A260690     7| . . . 1 1 . . . . . . . . . . . . . . . . . . . . .
%e A260690     9| . . . 1 1 1 1 1 . . . . . . . . . . . . . . . . . .
%e A260690    11| . . . . 1 2 1 1 1 1 1 . . . . . . . . . . . . . . .
%e A260690    13| . . . . 1 1 2 2 1 1 1 1 1 1 1 . . . . . . . . . . .
%e A260690    15| . . . . 1 1 2 2 2 2 1 1 1 1 1 1 1 1 1 . . . . . . .
%e A260690    17| . . . . . 1 1 2 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 . .
%e A260690    19| . . . . . 1 1 2 2 3 3 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
%e A260690    21| . . . . . 1 1 1 2 3 3 3 3 2 2 2 2 2 2
%e A260690    23| . . . . . . 1 1 2 2 3 4 3 3 3
%e A260690    25| . . . . . . 1 1 2 2 3 3 4 4
%e A260690    27| . . . . . . 1 1 1 2 2 3 4
%e A260690    29| . . . . . . 1 1 1 2 2 3     5
%e A260690    31| . . . . . . . 1 1 2 2
%e A260690    33| . . . . . . . 1 1 1 2
%e A260690    35| . . . . . . . 1 1 1 2
%e A260690    37| . . . . . . . 1 1 1 2
%e A260690    39| . . . . . . . . 1 1
%e A260690    41| . . . . . . . . 1 1
%e A260690    43| . . . . . . . . 1 1
%e A260690    45| . . . . . . . . 1 1
%e A260690    47| . . . . . . . . 1 1
%e A260690    49| . . . . . . . . . 1
%e A260690    51| . . . . . . . . . 1
%Y A260690 A264041 gives the terms along the main diagonal.
%K A260690 nonn,tabl
%O A260690 1,2
%A A260690 _Gabriella Pinter_ and _Jon E. Schoenfield_, Nov 15 2015