# Number of ways to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles

How many ways are there to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles? Rotating is allowed.

### Progress

Let $T_n$ be the number of ways; then $T_n = T_{ n-1} + T_{ n-2} + 1$ (based on removing one of tiles, as in quid's answer).

• Usually, in problems like this, you would try a few cases (say for $n$ from $1$ to $4$ or $6$ or something), and see if you can spot some pattern. Next, you would use that pattern to come up with a guess at a formula. Then comes the induction part of the proof, showing that the formula you have is indeed correct. You should at least try the cases yourself before coming here. – Arthur Dec 13 '14 at 19:15
• i guess the formula is this : T(k) = T(k-1) + T(k-2) + 1 . the parentheses are indices – ms95 Dec 13 '14 at 19:17
• Good. Together with $T(1)=1$ and $T(2)=3$, does that formula work for $k=3$ or $4$? – Arthur Dec 13 '14 at 19:21
• i guess it does – ms95 Dec 13 '14 at 19:22
• ok thanks i did the rest . thank you so much – ms95 Dec 13 '14 at 20:02

Consider the end (or start) there are three possibilities:

• $2 \times 1$ tile.

• $2 \times 2$ tile.

• two $1 \times 2$ tiles.

Removing these last tiles yields:

• a tiling of $2 \times (n-1)$ grid.

• a tiling of $2 \times (n-2)$ grid.

• a tiling of $2 \times (n-2)$ grid.

From this, and the first values, you get the recursive description that you can solve if you want something more explicit.

Added for the record:

• The recursion is $T_n = T_{n-1} + 2T_{n-2}$ and $T_1= 1$ and $T_2=3$.

• This sequence is known as Jacobsthal numbers, except for a shift of the index.

• The closed form is $$\frac{2^{n+1} - (-1)^{n+1}}{3}.$$

• Should be $T_n=T_{n-1}+2T_{n-2}$. – paw88789 Dec 13 '14 at 20:50
• Thank you so much! I schould have paid more attention when typing. – quid Dec 13 '14 at 20:56
• Out of curiosity, do you know of a combinatorial interpretation of the closed form? (I may ask that as a separate question...) – Steven Stadnicki Dec 13 '14 at 21:01
• @StevenStadnicki OEIS has several applications oeis.org/A001045 I would not know a "bijective proof" of the current problem at the moment. (But this does not tell much.) – quid Dec 13 '14 at 21:03