3
$\begingroup$

If I have a nx2 grid which I need to fill using 2x1 dominoes and L shaped trominoes in any combination, how many different combinations are possible?

I am aware that when only 2x1 dominoes are used then the cell definition using dynamic programming is: $$ f\left [ 0 \right ]= 0 $$ $$ f\left [ 1 \right ]= 1, i=1 $$ $$ f\left [ 2 \right ]= 2, i=2 $$ $$ f\left [ i \right ]= f\left [ i-2 \right ]+ f\left [ i-1 \right ], \forall i>2 $$

When L shaped trominoes are added to consideration, we (assume) can use them only in pairs since using odd number L shaped trominoes will leave one 1x1 grid unfilled. so when a pair of such trominoes combine it is equivalent to using a single 3x2 rectangular piece. Everytime we use $\ num=\lfloor n/3 \rfloor $ rectangular pieces and the rest are filled with 2x1 dominoes. Also the total number of combinations would be sum of twice the $\ num$, $\ f[i] $ and number of 2x1 domino combinations of the rest of the grid when the 3x2 piece is used. Is this assumption right? This is how far I have gotten through. If any of you have any hints it would be appreciated. Thank You in advance.

Note: Tile Rotations are allowed

Improve this question
$\endgroup$
5
  • $\begingroup$ You can use the same essence in the prototypical domino-tiling case. I'm not quite sure what the proper terminology is, but I'll use the term "irreducible" block to mean a block of dominoes that can't be vertically decomposed. So there's a single $2 \times 1$ irreducible block (just a domino lying flat), a single $2 \times 2$ block (two dominoes placed next to each other vertically), a single $2 \times 4$ block (two trominos placed together), and two $2 \times 3$ blocks (the two rotations of the do/tromino combo). Following the same intuition, you should be able to derive a similar recurrence. $\endgroup$
    – Lee
    Nov 29, 2016 at 20:28
  • $\begingroup$ Sorry I am not sure I follow. When two trominos are placed isnt the block a $\ 2 \times 3 $ block? $\endgroup$
    – Roshan SA
    Nov 29, 2016 at 20:42
  • $\begingroup$ Oops, my mistake. I accidentally visualized a tromino as a tall L shaped tile with 4 cells rather than a 3-celled corner. In this case, the situation is a bit more complicated. For example, you can construct an arbitrarily tall irreducible block of odd or even height. I'll elaborate on this later, but you should find that the $2 \times 3$ block can generalize to any $2 \times \rm odd$ blocks, etc. $\endgroup$
    – Lee
    Nov 29, 2016 at 21:10
  • $\begingroup$ Please edit the question to include all relevant information in the question itself. Don't just leave clarifications in the comments -- we want the question to stand on its own, so people don't have to read the comments to understand what you are asking. $\endgroup$
    – D.W. ♦
    Nov 30, 2016 at 1:36
  • $\begingroup$ This is a leetcode question with Solutions link at leetcode.com/problems/domino-and-tromino-tiling/solutions But overrall, it relies on the pattern found: f(n) = 2f(n−1)+f(n−3) $\endgroup$
    – Zheng Gu
    Dec 25, 2022 at 3:59

1 Answer 1

Reset to default
6
$\begingroup$

There is a mutual recursion in two variables $f(n)$ for the $n\times 2$ grid and $g(n)$ for the $n\times 2$ grid with a single square sticking out. It does not matter where the square sticks out (first or second row) because their number of tilings is the same.

domino and tromino

Note the trominos indeed come in pairs, but they do not need to form a $3\times 2$ block. You can place horizontal dominoes in between. Now that I look at it, it seems there is a recursion with one $f(n)$ if you look at a tromino and its matching partner. This picture suggests $f(7) = f(6)+f(5)+2f(4)+2f(3)+ \dots +2f(1)+2f(0)$. Sounds like a promising recursion to me.

enter image description here

If my initial computations are right, this suggests 1,1,2,5,11,24,53,117, ... which is OEISA052980. This lists another recurrence however. Would be fun if they match.

PS. Yes! Recursions are the same. $f(n) = f(n-1) + f(n-2) + 2\sum_{k=0}^{n-3} f(k)$. Then subtract $f(n)-f(n-1) = f(n-1)+f(n-3)$. Thus $f(n) = 2f(n-1)+f(n-3)$, which is in the OEIS.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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