0

I have a 3 x n rectangle. I need to find a generating function expressing the number of little 1 x 3 rectangles inside this bigger one. How can I do this? I have no idea how to even begin.

khernik
  • 1,369

2 Answers2

2

Hint: $a_{n+3} = a_n+a_{n+2}$.

Expanded: $a_n$ obviously, is the number of tilings of a $3\times n$ rectangle. Now, consider a $3\times (n+3)$ rectangle. In any tiling, the bottom left corner is either tiled by a vertical tile, or a horizontal tile. In the first case, the rest of the is $3 \times (n+2)$ and can be tiled $a_{n+2}$ ways. Otherwise, the cell just above the bottom left has to be tiled by a horizontal tile, and same for the one above it. In which case the rest is a $3 \times n$ rectangle, which can be tiled $a_n$ ways. These cases are obviously mutually exclusive.

The answer seems to be $$\sum_{n=0}^\infty a_n x^n = \dfrac{1}{1-x-x^3}$$.

ronno
  • 11,390
  • How? I don't know how to combine recurrence solution with this problem, could you describe this a bit please? I'll owe you one :P – khernik May 11 '13 at 11:37
  • Added the derivation of the recurrence relation, and the answer (assuming I did the calculations correctly). If you are not clear on the explanation, or how to proceed from there, feel free to ask. – ronno May 11 '13 at 12:23
  • Thank you very much, most of the things are clear to me now. So I get the recurrence equation (few first values and the recurrence formula), and I just have to solve this, and that's it? – khernik May 11 '13 at 22:29
  • Yes. I'm guessing you know how to solve such recurrences via generating functions. – ronno May 12 '13 at 03:43
-2

This is in particular equation (9) in Tilings of Rectangular Regions by Rectangular Tiles: Counts Derived from Transfer Matrices, ArXiv:1406.7788 by Richard J. Mathar.

R. J Mathar
  • 1