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


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).

  • 1
    $\begingroup$ 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. $\endgroup$ – Arthur Dec 13 '14 at 19:15
  • 1
    $\begingroup$ i guess the formula is this : T(k) = T(k-1) + T(k-2) + 1 . the parentheses are indices $\endgroup$ – ms95 Dec 13 '14 at 19:17
  • $\begingroup$ Good. Together with $T(1)=1$ and $T(2)=3$, does that formula work for $k=3$ or $4$? $\endgroup$ – Arthur Dec 13 '14 at 19:21
  • $\begingroup$ i guess it does $\endgroup$ – ms95 Dec 13 '14 at 19:22
  • 1
    $\begingroup$ ok thanks i did the rest . thank you so much $\endgroup$ – 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}.$$

  • $\begingroup$ Should be $T_n=T_{n-1}+2T_{n-2}$. $\endgroup$ – paw88789 Dec 13 '14 at 20:50
  • $\begingroup$ Thank you so much! I schould have paid more attention when typing. $\endgroup$ – quid Dec 13 '14 at 20:56
  • $\begingroup$ Out of curiosity, do you know of a combinatorial interpretation of the closed form? (I may ask that as a separate question...) $\endgroup$ – Steven Stadnicki Dec 13 '14 at 21:01
  • $\begingroup$ @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.) $\endgroup$ – quid Dec 13 '14 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.