login
A334396
Number of fault-free tilings of a 3 X n rectangle with squares and dominoes.
2
0, 0, 2, 2, 10, 16, 52, 104, 286, 634, 1622, 3768, 9336, 22152, 54106, 129610, 314546, 756728, 1831196, 4413952, 10667462, 25735346, 62160046, 150020016, 362257392, 874442064, 2111291570, 5096782418, 12305249242, 29706645280, 71719568260
OFFSET
1,3
COMMENTS
A fault-free tiling has no horizontal or vertical faults (that is to say, the tiling does not split along any interior horizontal or vertical line).
FORMULA
a(n) = a(n-1) + 4*a(n-2) - a(n-3) - a(n-4) for n >= 5.
a(n) = 2*A112577(n-2) for n >= 2.
G.f.: 2*x^3 / ((1 + x - x^2)*(1 - 2*x - x^2)). - Colin Barker, Aug 06 2020
EXAMPLE
a(4) = 2 because these are the only fault-free tilings of the 3 X 4 rectangle with squares and dominoes:
._ _ _ _ _ _ _ _
|_ _|_| | | |_|_ _|
| |_ _|_| |_|_ _| |
|_|_|_ _| |_ _|_|_|
MATHEMATICA
a[n_]:= (2/3)*(Fibonacci[n-1, 2] - (-1)^n*Fibonacci[n-1]);
Table[a[n], {n, 40}] (* G. C. Greubel, Jan 15 2022 *)
PROG
(PARI) concat([0, 0] , Vec(2*x^3/((1+x-x^2)*(1-2*x-x^2)) + O(x^30))) \\ Colin Barker, Aug 06 2020
(Magma) [n le 4 select 2*Floor((n-1)/2) else Self(n-1) +4*Self(n-2) -Self(n-3) -Self(n-4): n in [1..40]]; // G. C. Greubel, Jan 15 2022
(Sage) [(2/3)*(lucas_number1(n-1, 2, -1) - (-1)^n*lucas_number1(n-1, 1, -1)) for n in (1..40)] # G. C. Greubel, Jan 15 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved