21
$\begingroup$

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.

  • 2
    I'm not sure exactly how you're counting different "ways" to be the same, but depending on that definition this could be a very hard problem. (As in, open.)2010-07-29
  • 0
    I prefer no rotated duplicates but either way is okay. If it's an open problem, I'd like to see a reference. Someone must have studied something like this, right?2010-07-29
  • 1
    Even counting the number of partitions into dominoes (rectangles 2x1) is quite difficult -- see "Concrete Mathematics", ex. 7.51 for the answer and some hints; there exists (e.g. http://www.mccme.ru/free-books/matpros/ia129142.pdf.zip -- but it's in Russian) a proof that uses methods from http://arxiv.org/abs/math/9810091 and http://arxiv.org/abs/math/0108150.2010-07-29
  • 0
    Then should I repost this in MathOverflow?2010-07-29
  • 0
    @puri: no, I didn't mean duplicates, I mean the way you've phrased the question it's not clear whether you want to take length into account, etc. But if you were more specific I think this would be a fine question for MO.2010-07-29
  • 0
    No, I don't take length into accounts. Frankly I don't know how to rephrase the question to be more mathematically specific. This question is tagged "computer-science" because I am thinking of generating all of these patterns and objectively choosing the "best-looking" ones, and it would be nice to be able to take a look at all of them. If there is a solution, it's good. If not, I want to be sure that it is still a open problem. Then how about good approximation or related problems?2010-07-30
  • 1
    (Offtopic) solution(s) for the domino problem etc: http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/domino2010-07-30
  • 1
    At what coordinates may the dividing lines lie? If you allow real coordinates, there are infinitely many way to split any rectangle into two sub-rectangles. Is this rectangle made of nxn tiles, e.g.?2010-08-04
  • 1
    @Jens It doesn't matter where exactly the lines are. What matters is the overall form.2010-08-05
  • 0
    Given a square of side L that includes V vertical and H horizontal lines each of length L, then the number of internal rectangles is R = (V+1)(H+1). Now we can begin subtracting portions of these vertical and horizontal lines one at a time to subtract one internal rectangle (R -> R-1); but we can only remove portions of lines if this creates a rectangle and not some other shape (see the second diagram in the OP to make this clear). The problem now becomes related to counting the number of ways we can delete line portions without creating non-rectangle shapes inside the original square.2010-10-31
  • 0
    @IlmariKaronen Thanks for reporting the broken url. I cannot find the image in my computer or cached anywhere on the internet. I have removed the link above for now.2015-08-17

4 Answers 4

21

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.

alt text

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.

  • 0
    By the way, the recurrence involved counting tilings with a specific number of edges hitting the right side of the square and a specific number of places where 4 rectangles meet in a vertex.2010-10-31
  • 0
    1, 2, 6, 15 are exactly the numbers I have when I count by hands (including all rotations and reflections.) I will appreciate if you can share the recurrence relation or point me to a publication.2010-11-02
  • 0
    I've added a picture to show there are indeed 25 tilings with 4 rectangles.2010-11-02
  • 0
    Okay now I've added the recurrence relation!2010-11-02
  • 0
    @Jim Conant: On the third iteration, aren't the four last figures redundant since they are just rotations of the first two? By the way, your picture is so annoying to look at, I'm prey of the [grid illusion!](http://en.wikipedia.org/wiki/Grid_illusion) :D2011-02-18
  • 0
    @Raskolnikov: Yes the grid illusion is pronounced. :) To answer your question, the list includes rotations and reflections as distinct. I haven't tried figuring out a formula once you mod out by dihedral symmetries, but I bet it is even more complicated.2011-02-18
  • 0
    @Jim Conant: I can't tell from your picture what definition of "distinct tilings" you are using, because there is a question that first arises for five tiles. Look at the center tiling in the second row of your four-tile collection. How many distinct tilings can be formed by adding a single vertical edge to its topmost rectangle? Is it three, or just one (and what does your recurrence relation say)?2011-02-20
  • 0
    @mjqxxxx: If I understand you correctly, there would be three possible new tilings. One where the new edge is above the left part, one where it creates a 4-valent vertex, and one where it is above the right part. The definition of combinatorially equivalent could be phrased to say that there is a homeomorphism from one tiling to the other that is the identity on the 4 corners. (Or something.) I realize that I haven't explained the recurrence relation very well. Tim and I should really write this up into a paper.2011-02-20
  • 0
    @mjqxxxx: But to explain a little bit, the recurrence relation counts the number of ways of pushing an edge in from the right, so that in any particular tiling, to see what tiling it "comes from," you take a right-most vertical line segment and push it off the right side. There is a problem with this, though. There could be many "right-most" line segments, so there is overcounting. This is the role of the outside alternating summation. It is really an inclusion-exclusion in disguise, and accounts for overcounting.2011-02-20
  • 0
    @Jim Conant: Actually I was asking about the *fourth* tiling in the second row, where adding a vertical edge to the topmost rectangle can't form a 4-valent vertex. From your explanation I assume there is only one way to do that?2011-02-21
  • 0
    @mjqxxxx: Indeed.2011-02-21
  • 0
    I've edited the post to include a link to a paper that described this in more detail.2011-02-22
  • 0
    In the n=4 case, where is the tiling which is just 3 vertical cuts, i.e. 4 long vertical rectangles, i.e. 90-degree rotation of the first solution in n=4? Am I missing something?2018-05-22
  • 0
    @antkam: Well-spotted! I accidentally omitted that one and duplicated the last one and the 8th one in the list of $n=4$.2018-05-22
5

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.

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.

  • 0
    Interesting but I wonder if your graph representation will be sufficient. From the second example above, sliding the partitions the other way around from "clockwise" to "counter-clockwise" will result in another way to partition with the exactly same graph.2010-08-08
3

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?