# Tiling a $2 \times n$ rectangle by $2 \times 1$ rectangles and L-shapes : adapted generating functions

I have found the generating formula of $$A_n$$ = $$A_{n-1}$$+$$2A_{n-2}$$+$$2A_{n-3}$$+$$2A_{n-4}$$+$$2A_{n-5}$$ and I have found $$B_n$$=$$A_{n-2}$$+$$2A_{n-3}$$+$$2A_{n-4}$$+$$2A_{n-5}$$ (I think my formula for $$B_n$$ is probably wrong) I'm wondering if anyone can show me how to get to the formula $$A_n$$=$$2A_{n-1}$$+$$A_{n-3}$$ because I am quite lost. Any help would be appreciated

• Please explain how you get your formulas for $A_n$ and $B_n$. I don't see how these can be true. The formula for $A_n$ suggests that we always have a $2\times m$ rectangle on the left or right, but this isn't so. I can start with an L-shaped piece on the left, then put straight pieces in like bricks in a wall for as long as I like, and finish off with the opposite L-shaped piece. There is no tiled sub-rectangle. Am I overlooking something? May 12, 2020 at 14:10
• I have taken the liberty to change your title into a more significant one in order to convey the main ideas (the former word "domino" was misleading, especialy because there is anotheer L shape wich has definitely not the shape of a domino). May 12, 2020 at 15:23

Let $$n\geq 2$$. For any division of the $$2\times n$$ rectangle or the $$n+(n+1)$$ blocks, removing the leftmost pieces (either a vertical domino, and L shape, or two horizontal dominos) gives another shape whose number of divisions is known. More specifically, I got $$A_n=A_{n-1}+2B_{n-2}+A_{n-2},\\ B_n=B_{n-1}+A_{n-1}.$$ Here are the details:

For a $$2\times n$$ rectangle: if the leftmost piece is a vertical domino, then removing it gives a $$2\times(n-1)$$ rectangle; if the leftmost piece is an L shape then it can either be L or $$\Gamma$$, and removing it gives a $$(n-2)+(n-1)$$ shape; and if the leftmost pieces are two horizontal dominos, then removing them gives a $$2\times (n-2)$$ rectangle.

For a $$n+(n+1)$$ shape: if the leftmost piece is a domino (half of it is sticking out), then removing it gives a $$n+(n-1)$$ shape; if the leftmost piece is an L shape (but backwards), then removing it gives a $$2\times (n-1)$$ rectangle.

Using these two formulae and basic arithmetic on generating functions, we can obtain $$A(t)=2tA(t)+t^3A(t)$$, which gives us the desired relation. If you want, I can explicit these calculations as well.

## Calculating $$A(t)$$

We will be using the fact that two sequences $$(x_n)_n$$ and $$(y_n)_n$$ are equal iff the formal generating series $$\sum x_nt^n$$ and $$\sum y_nt^n$$ are equal, and that $$t\sum x_nt^n$$ corresponds to the sequence $$(x_{n-1})_n$$, with $$x_{-1}=0$$.

First, $$B(t)=tB(t)+tA(t)+B_0$$ and $$B_0=0$$, so $$B(t)=\frac{t}{1-t}A(t)$$. Therefore \begin{aligned} A(t)&=tA(t)+t^2A(t)+2t^2B(t)+A_0\\ &=\left(t+t^2+2t^2\frac t{1-t}\right)A(t)+A_0\\ &=\frac{t+t^3}{1-t}A(t)+A_0, \end{aligned} so $$(1-t)A(t)=(t+t^3)A(t)+(1-t)A_0,$$ so $$A(t)=2tA(t)+t^3A(t)+(1-t)A_0,$$ so for all $$n\geq 3$$, $$A_n=2A_{n-1}+A_{n-3}$$.

• Please indicate how to get $A(t)$. I got the formulas for $A_n$ and $B_n$ myself, but haven't been able to get any further. May 12, 2020 at 14:22
• @saulspatz I added my calculations. I'm don't do generating series that often, so maybe I made a mistake. May 12, 2020 at 14:38
• Looks right to me. Thanks. May 12, 2020 at 15:01
• A very good text on enumerative combinatorics addressing as well this kind of issues : arxiv.org/pdf/1409.2562.pdf May 12, 2020 at 15:19
• see the same question here and here. May 12, 2020 at 15:42