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