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

Author

Greg Dresden and Oluwatobi Jemima Alabi, Jul 06 2020

Keywords

• nonn
• easy

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).

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).

Crossrefs

Cf. A084477, A084479, A084481, A112577, A124997, A335747.

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