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

Question

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be:

      f(n) = 4f(n-1) - 2f(n-2)  
where f(0) = 1  
  and f(1) = 1 

but the recurrence relation only counts the cases in which at least one side (either top, bottom, left or right of the original rectangle) is not split into sub-rectangles. There are many other partitions that don't belong to those simple cases like

[EDIT ImageShack has removed the picture. One of the cases is the sixth partition when n = 4 in the picture in the accepted answer below.]

Any other related problem suggestions are welcome. Also it is nice to know how to traverse this partition efficiently.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

Here is a non-answer which may prove interesting and tractable.

Given a configuration of rectangles that properly tile a surrounding rectangle, one can represent the tiling in a number of ways. Two that come to mind I will call C and LL. C represents each rectangle by giving its dimensions (x-span and y-span) and the coordinates for the center of the rectangle, and LL does the same, except it specifies the coordinate for the lower left vertex (instead of the center) of each rectangle.

With plenty of rectangles in a tiling, there is some redundancy in the LL form of a tiling. For example, it should be possible to deduce the dimensions of the rectangle in the extreme lower left corner of the tiling by noting stored coordinates of the rectangle above and the rectangle to the right of this corner rectangle. No such boundaries exist for the upper rightmost rectangle in a tiling, but perhaps an "end point" could be added to indicate the maximum x and maximum y values in the tiled rectangle. Suppose we add such an end point, and let LL' be a representation like LL that contains the lower left coordinates and the end point, and does NOT contain the dimension information.

Statement 1: LL' is an equivalent representation to LL. That is, given a representation in LL form, one can construct a representation in LL' form and use it to recreate the tiling; conversely, one can build an LL form from an LL' form to represent the same tiling.

Statement 1 appears to be true; it is clear how to make an LL' form from an LL form, while for the converse, it should be possible to check all the lower left points to see which would help determine the dimensions for a given rectangle.

Is statement 1 true?

Now consider C and make C' from C by again forgetting the dimensions, except that you can provide two endpoints representing the upper right and lower left corners of the tiled rectangle.

Statement 2: C and C' are equivalent in the sense used above for LL and LL' .

It is clear how to get a C' form from a C form. It is NOT clear that it is possible to get a C form from a C' form where you have no dimension information at all, except for the entire rectangle as implied by the two endpoints.

Is Statement 2 true?

Statements 1 and 2 have a bearing on the problem above: it may be possible to enumerate geometrically inequivalent tilings with n rectangles by looking at normalized forms of either C, C', LL, or LL'. Also, there may be advantages to switching between the forms of the tiling in determining equivalence.

There are interesting variations that can occur. For example, C'' might have the center of the tiled rectangle instead of the two endpoints, or even give just the dimensions of the tiled rectangle instead of the coordinates for its upper right and lower left corners. What information is lost by such representations?

Meta-question: Is there a geometric property at work here that might explain why LL' uses less information but is still equivalent to C (assuming Statement 1 is true), while C' does not (assuming Statement 2 is false)? Can something be said in general about what properties of a form for tiling are needed in order to represent the tiling both minimally and faithfully?