One useful distinction (already used by a previous contributor) is to distinguish whether a partition intersects a side. Let F(N, M) be the number of partitions of an NxM rectangle, G(N, M) be the number of internal partitions and H(N, M) the number of partitions that intersect a side (excluding rotations and reflections). Then

F(N, M) = G(N, M) + H(N, M)

Since the internal partitions for an NxM rectangle is one more than the set of all partitions for a (N-2)x(M-2) rectangle, we also have

G(N, M) = F(N-2, M-2) + 1

(Note – the reason for the +1 term is that the (N-2)x(M-2) rectangle taken as a whole counts toward G(N, M), but not toward F(N-2, M-2). Note as well that for our later argument, it will be useful to imagine the internal partitions on the left side of the rectangle.)

Now, starting from the bottom left and proceeding counterclockwise while skipping corners; index the external nodes from 1 to 2N + 2M - 4. We see then that H(N, M) is the number of routes starting at any index between 1 and T(N) = [(N-1)/2] (here [] indicates the greatest integer less than function) and terminating at a higher index, subject to the constraints that we avoid closed loops and the insistance that none of the intermediary nodes are external (indexed).

From this we see that it is of interest to investigate the number of simply connected routes between two points. We will also discover that it is especially useful to determine a formula for the number of non-trivial (that is, with length > 1) simply connected routes from a given point to it’s nearest neighbours.

Note first that there is only a single internal route connecting two points adjacent to a corner. (That is, for nodes 1 and 2N + 2M – 4). This is an exception case among the node pairs contributing to H(N, M). More generally, with N, M each exceeding 2 there will be multiple routes connecting external nodes.

How many such routes are there? Consider any internal partition passing through the node immediately above the starting node. We have the choice of passing this internal partition either on the left or the right. Hence, (with the exception cited above) the number of routes through an SEC is one more than twice the number of internal partitions passing through the node one step north of the starting point. (The +1 term is needed to account for a "direct connection" in the absence of any relevant internal partitions).

How many internal partitions pass through the node one step north? This is the same as the number of simply connected routes between starting point and a neighbour neighbouring point on a N-2 X M-2 grid, excluding trivial (length one) routes but (this time) allowing paths along external edges.

The motivation will be to continue in this way is to derive a recursion relation for H...