1

my professor assigned as extra credit (and the due date has passed) but I'm still curious as to how I could go about doing this. Basically the goal is to find the amount of possible patterns there are for a 3xn grid being filled with $2\times 1$, $1\times 2$ and $1\times 1$ blocks Solving for the $3\times n$ grid using $2\times 1$ blocks is easy, but I can't figure out how to extend it to include the $1\times 1$ blocks. Here is a picture of the assignment sheet in case the description I provided is not good enough

Right now I know that the relation for a $3\times n$ with $2\times 1$ tiles is

  1. $f(n) = f(n-2) + 2g(n-1)$
  2. $g(n) = f(n-1) + g(n-2)$
  3. $f(0) = 1$
  4. $f(1) = 0$
  5. $g(0) = 0$
  6. $g(1) = 1$

I'm just having trouble breaking the problem down for the $3\times n$ with $2\times 1$ blocks and $1\times 1$ blocks. I'm particularity having trouble creating the base cases for such an operation, as finding the functions themselves is similar to the first problem.

Photo of the Assignment Page:

enter image description here

Euler88 ...
  • 2,090
user3421045
  • 11

1 Answers1

0

Draw a vertical line after the $m$th column of the $3\times n$ rectangle. It will bisect (or not) some horizontal $1\times2$ dominoes.
There are eight possible sets of dominoes it will bisect, from none of them to all three. Form a recursion for all eight sets. They will be in terms of each other, you need to build an $8\times8$ matrix, call it $M$.
The initial case is the $3\times0$ matrix, where one of the eight sets (no bisections) has 1 solution and all the rest have none. Call the vector $v=(1,0,0,...,0)^\top$.

Then the number of solutions comes from $M^n v$

Empy2
  • 50,853