Tiling a $3 \times 2n$ rectangular shape with dominoes

I'm aiming to figure out if there's any kind of very easy means to compute the variety of means to floor tile a $3 \times 2n$ rectangular shape with dominoes. I had the ability to do it with both codependent reappearances

f(0) = g(0) = 1
f(n) = f(n-1) + 2g(n-1)
g(n) = f(n) + g(n-1)

where $f(n)$ is the real solution and also $g(n)$ is an assistant function that stands for the variety of means to floor tile a $3 \times 2n$ rectangular shape with 2 added squares on completion (the like a $3 \times 2n+1$ rectangular shape missing out on one square).

By incorporating these and also doing some algebra, I had the ability to lower this to

f(n) = 4f(n-1) - f(n-2)

which turns up as series A001835, validating that this is the proper reappearance.

The variety of means to floor tile a $2 \times n$ rectangular shape is the Fibonacci numbers due to the fact that every rectangular shape finishes with either a verticle domino or 2 straight ones, which offers the specific reappearance that Fibonacci numbers do. My inquiry is, exists a comparable straightforward description for this reappearance for tiling a $3 \times 2n$ rectangular shape?

0
2019-05-06 21:35:49
Source Share
Answers: 1

Here's my ideal contended the type of description you're requesting for, although it's not virtually as clear as the $2 \times n$ instance. The adverse indicator makes combinatorial evidence hard, so allow's reposition this as :

$$f(n) + f(n-2) = 4f(n-1)$$

Then you intend to show that the variety of $n$ - tilings, plus the variety of $(n-2)$ - tilings, is 4 times the variety of $(n-1)$ - tilings. (An "n - tiling" is a tiling of a $3 \times 2n$ rectangular shape by dominoes.)

In bijective terms, after that, we desire a bijection in between the set of $n$ - tilings and also $(n-2)$ - tilings and also the set of $(n-1)$ - tilings, where the $(n-1)$ - tilings are each marked with the number $1, 2, 3,$ or $4$.

Offered an $(n-1)$ - tiling, there are 3 "noticeable" means to get an $n$ - tiling from it, particularly by including among the 3 $1$ - tilings on the appropriate end These create tilings which have an upright line passing right via, 2 devices from the appropriate end ; call these "faulted" tilings, and also those which do not have an upright line because placement "impeccable".

So it is adequate to show that the variety of impeccable $n$ - tilings, plus the variety of $(n-2)$ - tilings, is the variety of $(n-1)$ - tilings. It's very easy to see that the variety of impeccable $n$ - tilings is $2g(n-2)$ ; an impeccable tilings have to have a straight domino covering the 2nd and also 3rd squares from the right in some row, and also this presumption compels the positioning of a few other dominoes. So we require $2g(n-2) + f(n-2) = f(n-1)$. Changing the indices, we require $2g(n-1) + f(n-1) = f(n)$, which you have actually currently claimed holds true.

0
2019-05-08 19:15:33
Source