Number of ways to partition a rectangle into n sub-rectangles

I had my student, Tim Michaels, work on this. We came up with a complicated recurrence relation, indicated below. The first few answers are 1, 2, 6, 25, 128, 758, 5014, 36194, 280433, 2303918, 19885534, 179028087, 1671644720, 16114138846, 159761516110, 1623972412726, 16880442523007, 179026930243822, 1933537655138482, 21231023519199575, 236674460790503286, 2675162663681345170, 30625903703241927542, 354767977792683552908, 4154708768196322925749, 49152046198035152483150, 587011110939295781585102, 7072674305834582713614923. Note that we are counting rotations and reflections as distinct tilings. An interesting pattern is that mod 2, there is an 8-fold periodicity which we don't understand and can't prove in general.

Here's a picture of the cases n=1,2,3,4, with 1,2,6,25 tilings in each case.The way to systematically generate these is to "push in" a vertical line from the right to all previously constructed tilings in all possible ways. That's how the recurrence relation is defined.

Okay, here is the recurrence: Let $a_{\ell,j,m}$ be the number of distinct tilings with $\ell$ tiles, $j$ edges that meet the right-hand side of the square and $m$ 4-valent vertices. $$a_{\ell,j,m}=\sum_{p=1}^\ell(-1)^{p+1}\sum_{i=0}^m\sum_{n=1}^{\ell-1}\sum_{k=0}^{n-1}\alpha_{n,k,i,\ell,j,m,p} a_{n,k,i}$$ where, letting $t=m-i, s=\ell-n-p-t$ and $r=k+s+t+p-j$, $$\alpha_{n,k,i,l,j,m,p}=\binom{r-1}{p-1}\binom{k-r+2}{p}\binom{s+r-1}{r-1}\binom{r-p}{t}.$$

Edit: I have posted a preprint describing the recurrence relation here. Comments are welcome. Is this sort of thing publishable anywhere to anyone's knowledge?

Edit 2: Nathan Reading has just posted a relevant preprint. He finds a bijection between generic tilings (no 4-valent vertices) and a set of permutations that avoid a certain pattern.

Edit 3: The paper has been published in the Annals of Combinatorics.

This problem is tantalizing. It may be a "toy"-version of some substantial ongoing research in topology, so it's valuable and interesting. It has immediate analogs in areas of classical topology, knot theory, universal algebra, and topological field theory. By toy-version, I don't mean it's necessarily easy to solve, but that it can be used to present some advanced ideas in a non-technical way. Forgive me because what follows is not an answer to your question, but a rambling list of related problems and possible applications. I only hope it inspires someone here to investigate the connections in algebraic topology. (Thus, community wiki.)

You are asking to count equivalence classes of parametrized rectangle framings (where a parametrized framing is a framing with precise line positions). In some sense, this type of enumeration problem comes up often in algebraic topology when one wants to understand a cellular decomposition of a complicated space. Take for instance, the space of n-planes in R^d. These spaces are called Grassmannians and their topology can be analyzed by breaking them down into subsets of various dimensions. These subsets are called Schubert cells. Counting these Schubert cells and understanding how they fit together was an important advancement. See the wikipedia entries on Grassmannian and Enumerative Geometry.

Your parametrized rectangle framing spaces (denoted perhaps Fi^{n} where i indexes the equivalence classes of framings having n sub-rectangles) are analogous to the cells of the Grassmannian, but the resulting stratified space is some universal space of parametrized rectangular framings which includes framings with an arbitrarily large but finite number of sub-rectangles. That is, each of your framing spaces F (the equivalence classes you want to count) represents a "cell" of some fixed dimension which degenerates into lower degree framings at the boundaries. By carefully studying the simple shape of each cell and how they degenerate into other cells, we can create a universal space $F^{\infty}$ = $\bigcup$ $F^{n}_{i}$ (modulo the boundary case equivalence relations).

Sometimes one can approach the topology of this universal space by other means, and that global knowledge can be used to count the number of cells needed in each stratum. Finally, as you point out, the spaces have certain symmetries which may pass up to the full space in an interesting way.

This stratification trick comes up all the time If you want to understand some large space, find a way to break it down into strata which fit together in an analyzable way. Or, find a related space which has a natural stratification, analyze this stratified space, and make inferences about the original space. A great, non-trivial use of this in the 90's was when Vassiliev realized that knots could be studied by analyzing the space of non-knots which admitted a very clear stratification (essentially stratify the non-knots by the number of points where the circle map is non-injective) Vassiliev found clear topological structure in this space and this allowed him to make claims about the structure of the set of knots. This led others like Kontsevich and Bar Natan to provide real computational tools using tricks for counting and integrating over cells. For instance, Mathworld has two good introductory articles on Vassiliev Invariants and Kontsevich Integrals.

Thirdly, your rectangle framing space is evocative of the little-disks operad which encodes an algebraic structure. See the wikipedia page:
http://en.wikipedia.org/wiki/Operad_theory#.22Little_something.22_operads

Whenever we have a set of topological spaces such that elements of the spaces can be geometrically combined to get higher degree spaces, it hints that the geometry can be studied using techniques from algebra. If you imagine putting variables in each of your frame's sub-rectangles, you've sort of described an algebraic operation. Imagine that every one of your parametrized n-framings defined a map from n inputs to 1 output, an "n-ary operation." Further assume that the geometry forces some consistency condition that demands that when you place the result of a p-ary operation into one of the sub-rectangles in a q-ary frame, you get just what you'd get from the corresponding (p+q-1)-ary frame operation. This means your algebra must satisfy certain standard relations (maybe up to homotopy) and then these operations may descend to operations on an appropriately defined cohomology theory. That is, the topology of your universal framing space may index various operations which satisfy certain relations exactly. See for instance the ncatlab.org entries on operad, L-infinity-algebra, and A-infinity-algebra.

I don't have enough rep to comment yet, so I'll make this CW since it's not a complete answer, just a remark.

Would it overcome some of the difficulty by using some sort of graph representation of the subdivided rectangle? Each rectangle is a vertex and an edge represents sharing a side, i.e. the first rectangle above would be represented by the edges ${(1,2),(1,3),(2,4),(3,4)}$ and the second by ${(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)}$, numbering the rectangles from top-left to bottom-right. The tricky part here would then be to implement the operations for subdividing by a vertical or horizontal line segment. Starting instead with lines instead of segments could be promising.