A335747 Number of ways to tile vertically-fault-free 3 X n strip with squares and dominoes.

1, 3, 13, 26, 66, 154, 380, 904, 2204, 5286, 12818, 30854, 74636, 179948, 434820, 1049122, 2533818, 6115538, 14766868, 35646080, 86064196, 207766110, 501609946, 1210964110, 2923573588, 7058053972, 17039774268

Offset: 0

Author

Greg Dresden and Oluwatobi Jemima Alabi, Jun 20 2020

Keywords

• nonn

Comments

By "vertically-fault-free" we mean that the tilings of the 3 X n strip do not split along any interior vertical line. Here are two of the 66 possible vertically-fault-free tilings of a 3 X 4 strip with squares and dominoes:

. _ _

| |_ | | _|_| |

|| _| | | | |_|

|| _|| ||_| |

Examples

			a(2) = 13 thanks to these thirteen vertically-fault-free tilings of a 3 X 2 strip:
._ _     _ _     _ _     _ _     _ _     _ _     _ _
|_ _|   |_|_|   |_|_|   |_ _|   |_|_|   |_ _|   |_ _|
|_|_|   |_ _|   |_|_|   |_ _|   |_ _|   |_|_|   |_ _|
|_|_|   |_|_|   |_ _|   |_|_|   |_ _|   |_ _|   |_ _|
._ _     _ _     _ _     _ _     _ _     _ _
|_ _|   |_ _|   |_ _|   | |_|   |_| |   | | |
| |_|   |_| |   | | |   |_|_|   |_|_|   |_|_|
|_|_|   |_|_|   |_|_|   |_ _|   |_ _|   |_ _|
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,4,-1,-1).

Crossrefs

Cf. A033506 (which gives all tilings of 3 X n strip), A112577, A134438, A291227.

Cf. A000045, A000129.

Programs

Magma

I:=[26, 66, 154, 380]; [1,3,13] cat [n le 4 select I[n] 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

CoefficientList[Series[(1+2x+6x^2+2x^3-8x^4+x^6)/((1+x-x^2)(1-2x-x^2)), {x, 0, 26}], x] (* Michael De Vlieger, Jul 03 2020 *)
LinearRecurrence[{1,4,-1,-1}, {1,3,13,26,66,154,380}, 40] (* G. C. Greubel, Jan 15 2022 *)

Sage

def P(n): return lucas_number1(n,2,-1)
def A335747(n): return (1/3)*(-9*bool(n==0) - 3*bool(n==1) + 3*bool(n==2) + 2*(3*P(n+1) + 2*P(n-1)) + 2*(-1)^n*fibonacci(n-1))
[A335747(n) for n in (0..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 >= 7.

a(n) = 2*A291227(n) - 8*A112577(n-2) + 2*A112577(n-4) for n >= 4.

a(n) = (2/3)*(A221174(n+1) + (-1)^n*A000045(n-1)) for n >= 3. - Greg Dresden, Jul 03 2020

G.f.: (1 + 2*x + 6*x^2 + 2*x^3 - 8*x^4 + x^6) / ((1 + x - x^2)*(1 - 2*x - x^2)). - Colin Barker, Jun 21 2020

a(n) = (1/3)*(-9*[n=0] - 3*[n=1] + 3*[n=2] + 2*(3*A000129(n+1) + 2*A000129(n-1)) + 2*(-1)^n*Fibonacci(n-1)). - G. C. Greubel, Jan 15 2022