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 That's puzzling (to Charlie) by FrankM)

I can't really follow what is being said in your description. I imagine I might have been able to understand it better if you could have included illustrations, but that's not possible here.

I do note your sentence "We will show that there is a subset of paths whose cardinality includes a term in M^7".  Of course a subset can be very much smaller in cardinality than the whole set. I don't know if that's the cause of the discrepancy here, as I can't follow the argument.  Also, even a series for an exponential function includes along the way a term with a seventh power, but then goes on to infinitely high powers.  I can't tell if this applies to your argument either.

Note that in my second posting, I present the exact numbers for cases up to M=29, and I link to the On-line encyclopedia of integer sequences, where the formula given is also recursive. No closed form solution is given.  I would think that if one existed, Sloane would have it. They present it in the form of adjacent squares, emphasizing the green area rather than its boundary (and calling it red, apparently for historical reasons, in some prior person's presentations).

Posted by Charlie on 2008-03-29 01:37:26