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

(In reply to Am I missing something? (spoiler?) by Charlie)

Charlie,

I'll start with a few personal remarks.

I enjoyed very much reading your comment. We've covered much the same ground, but I found your presentation is much clearer and better than my own.

I've reflected on this and decided the reason is the patchwork approach I've taken. Initially I set out to find a closed form solution. I succeeded, but the result was clumsy and inelegant. Besides, the task was more tedious than I thought would be appropriate for the site. So I decided to descope and only ask for the leading term. At this point I should have sought a new and different solution appropriate for the new challenge. Instead I merely cut out what was unnecessary from the earlier analysis. It still may do the job, but as far as my objective of elegance goes, it falls far short of the mark.

____________________

I've read your remarks, that the number of paths grows at least as fast as 2^M and, frankly, I haven't been able to find any essential fault with it. At the same time, I've re-examined my own result, showing growth like M^7 and here too, all seems good to me. Obviously, I'm missing something. So I've decided to publish my solution first here as a comment. I hope you and I (and any other who is interested) together can clear up the confusion.

Approach:
We will show that there is a subset of paths whose cardinality includes a term in M^7

Let w = {ak, bk} with k going from 1 to p, be an increasing sequence of integers between 0 and M. We will use w as an index to identify subsets of the set of closed paths in the 2xM rectangle. We want to tally the number of simply connected closed paths corresponding to each w and sum these over the range of possible ws.

Draw each of the intervals [ak, bk] along X=0. Add horizontal segments in the left column along each of Y = ak and each Y = bk. Next, add a "backbone" in the right column. That is, a rectangle including at least the range from Y= b1 - 1 to Y= ap + 1. Finally remove each of the segments [ak, bk] along X=1. We want to characterise the number of paths that can be generated by this procedure.

The trace of the path along X=2 is one continuous segment with lower edge beginning at any Y value between 0 to b1 - 1; while the upper edge may begin at any Y value going from ap + 1 to M. Therefore, the number of possible configurations in the right column is

F1 = (M - ap) b1

F1 is thus the number of simply connected closed paths corresponding to a given w.

How many w correspond to a given (b1, ap) combination? For every Y value in the range (b1 +1, ap - 2) we can independently choose to lie either along X=0 or X=1. Thus the number of possible arrangements of the space between b1 and ap is

F2 = Max( 2^[ap - b1 - 2], 1)

In addition, a1 can be any value from 0 to b1 - 1 and bp can be any value from ap + 1 to M. Thus, the number of arrangements of the left column for fixed (b1, ap) is F1 F2

We therefore have
# Paths of this type = Sum (M - ap)^2  Sum b1^2 Max( 2^[ap - b1 - 2], 1)

where the inner sum (over b1) goes from 1 to ap -1, and the outer sum (over ap) goes from 2 to M-1. We separate the term in the inner sum corresponding to b1=ap-1 from the remaining terms, then limit our attention to the latter terms, so that:

# Paths of this type > Sum 2^(ap-2) (M - ap)^2   Sum b1^2 / 2^b1

Now, the sequence L^2/2^L from L = 1 to N is known to sum to

(N^4 - 6N^3 + 21 N^2 - 26N + 12)/2^(N+1), so

# Paths = Sum (M - ap)^2 ap^4 + lower order terms.

(here the power of 2 term from the inner summation cancels with the 2^(ap-2) already in the outer summand.)

But this includes a sum over ap^6, and Sum ap^L (summed from ap = 1 to M) is known to produce a term in M^(L+1), verifying the result.

Posted by FrankM on 2008-03-28 21:28:58