login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer 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
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..78.

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.

Jon E. Schoenfield, [TEMPORARY PLACEHOLDER FOR] Proof of lower bound on D(w,h) where w and h are both odd

Jon E. Schoenfield, D(w,h) and K(w,h) tables [NEEDS IMPROVEMENTS FOR READABILITY]

Jon E. Schoenfield, Illustrations of various optimal solutions with both dimensions odd [NEEDS BETTER PLACEMENT OF PAGE BREAKS]

FORMULA

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.

EXAMPLE

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

CROSSREFS

A264041 gives the terms along the main diagonal.

Sequence in context: A194335 A026099 A049727 * A060802 A132073 A087817

Adjacent sequences:  A260687 A260688 A260689 * A260691 A260692 A260693

KEYWORD

nonn,tabl

AUTHOR

Gabriella Pinter and Jon E. Schoenfield, Nov 15 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 15 20:10 EST 2018. Contains 318154 sequences. (Running on oeis4.)