Combinatorics – Number of Ways to Partition a Rectangle into n Sub-Rectangles

combinatoricscomputer sciencerecurrence-relations

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.

Best Answer

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.

Related Question