Show that the number of simply connected closed paths through a 2xM rectangle grows at least as fast as M⁷.

Some clarifications:

A path is simply connected if it does not contain any closed subpaths.

The 2xM rectangle encompass points [x,y] in the Cartesian plane with:

0 ≤ x ≤ 2 and 0 ≤ y ≤ M

Paths are constructed within the 2xM rectangle from vertical and horizontal segments connecting points with integral values in x and y.

An alternative statement of the problem is to show that the number of paths/M⁷ > 0 as M goes to infinity.

The boundary of the green area is just one such closed loop.

y ↑M . ... ... . 2 1 0 1 2 x

Among the paths for a given M, some will extend all the way from y=0 to y=M, therefore having a height of M. Others that will fit within the grid are those of shorter heights, with those of height h being able to be positioned in any of (M+1-h) levels within the grid.

As M changes to M+1, any previous path that used the full height M that had the left side (x=0 to x=1) drawn in, or had the full width drawn in, will allow a new full height M+1 to be created. Similarly for either the right or the full width leading to another right-only top. A full width path of full height M+1 can be made from any of the three types of full-height M paths: left, right or both.

The table below was constructed with the above recurrence relations. The first row was created manually for M=1, and the remainder by computer program, shown below. There's a square on the left, a square on the right, or a rectangle that covers both, for a total of 3.

The next row, for M=2 allows us to follow the recurrences mentioned. The single square at the left from row 1, or the rectangle with both squares of height 1, can be extended to produce 2 possible paths that have only the left side at the top drawn. Similarly for the right only. The height-1 rectangle can be extended to a square, and the single-squares of height 1 can be extended to upside-down L's, either forward or reflected, giving three paths of height exactly 2 that have the whole width (2) used at the top.  This makes 7 altogether of paths that are exactly 2 high. One can see that this is correct, as: 1 2x2 square, 4 L shapes lacking one of the four subsquares, and 2 vertical rectangles (left and right). To this are added the height-1 values, either at the base or moved up one level, giving a total of 13 possibilities.

         top         top          top          total
 M     at left     at right    along both   Exact height    total  ratio to previous
 1           1           1           1            3             3
 2           2           2           3            7            13  4.33333333
 3           5           5           7           17            40  3.07692308
 4          12          12          17           41           108  2.70000000
 5          29          29          41           99           275  2.54629630
 6          70          70          99          239           681  2.47636364
 7         169         169         239          577          1664  2.44346549
 8         408         408         577         1393          4040  2.42788462
 9         985         985        1393         3363          9779  2.42054455
10        2378        2378        3363         8119         23637  2.41711831
11        5741        5741        8119        19601         57096  2.41553497
12       13860       13860       19601        47321        137876  2.41481014
13       33461       33461       47321       114243        332899  2.41448113
14       80782       80782      114243       275807        803729  2.41433288
15      195025      195025      275807       665857       1940416  2.41426650
16      470832      470832      665857      1607521       4684624  2.41423695
17     1136689     1136689     1607521      3880899      11309731  2.41422385
18     2744210     2744210     3880899      9369319      27304157  2.41421807
19     6625109     6625109     9369319     22619537      65918120  2.41421554
20    15994428    15994428    22619537     54608393     159140476  2.41421442
21    38613965    38613965    54608393    131836323     384199155  2.41421394
22    93222358    93222358   131836323    318281039     927538873  2.41421372
23   225058681   225058681   318281039    768398401    2239276992  2.41421363
24   543339720   543339720   768398401   1855077841    5406092952  2.41421359
25  1311738121  1311738121  1855077841   4478554083   13051462995  2.41421358
26  3166815962  3166815962  4478554083  10812186007   31509019045  2.41421357
27  7645370045  7645370045 10812186007  26102926097   76069501192  2.41421356
28 18457556052 18457556052 26102926097  63018038201  183648021540  2.41421356
29 44560482149 44560482149 63018038201 152139002499  443365544387  2.41421356

We see that the sequence of all paths for M=1, 2, ... is 3, 13, 40, 108, 275, etc. This is sequence A059020 in Sloane's online encyclopedia of integer sequences, which points out that another recursion formula would be  a(n)=2a(n-1)+a(n-2)+4n-1, so as to necessitate keeping only two generations back, rather than all the way back to the beginning of the table the way I did in the program shown below.

The last column above shows the ratio of the value for each M to the value for M-1. This approaches sqrt(2)+1. The ratio of the number of paths to (sqrt(2)+1)^M approaches 3.51776695.

DEFDBL A-Z
CLS
max = 29
DIM ofHeight(max)

level = 1
leftOnly = 1: rightOnly = 1: both = 1: ofHeight(1) = 3: tot = 3
FOR level = 2 TO max
 newLeft = leftOnly + both
 newRight = rightOnly + both
 newBoth = leftOnly + rightOnly + both
 leftOnly = newLeft
 rightOnly = newRight
 both = newBoth
 totExact = leftOnly + rightOnly + both
 ofHeight(level) = totExact
 prevTot = tot
 tot = 0
 FOR i = 1 TO level
  tot = tot + ofHeight(i) * (level + 1 - i)
 NEXT
 PRINT USING "### ########### ########### ########### ############ ############# ##.########"; level; leftOnly; rightOnly; both; ofHeight(level); tot; tot / prevTot
NEXT

 

Edited on March 28, 2008, 2:52 pm

Edited on March 28, 2008, 2:54 pm

Posted by Charlie on 2008-03-28 14:50:35