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?
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.
Related questions