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).
LINKS
Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,4,-1,-1).
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
Greg Dresden and Oluwatobi Jemima Alabi, Jul 06 2020
STATUS
approved