A334396 Number of fault-free tilings of a 3 X n rectangle with squares and dominoes.
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
Examples
a(4) = 2 because these are the only fault-free tilings of the 3 X 4 rectangle with squares and dominoes: ._ _ _ _ _ _ _ _ |_ _|_| | | |_|_ _| | |_ _|_| |_|_ _| | |_|_|_ _| |_ _|_|_|
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).
Programs
-
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
-
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 *) -
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
-
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
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
Comments