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 A similar conclusion by Paul)

There are actually only two ways to "decorate" an end where only the left or only the right side is at the end, as you can't add a right square to an end that has only a left square and vice versa.

As I noted in my second post, the value approaches 3.51776695 * (1+sqrt(2))^M, which is indeed exponential, but the base is less than the 3 that you indicate.

Posted by Charlie on 2008-03-28 20:25:01