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,2

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:

._ _ _ _ _ _ _ _

|_ _|_ _| |_ _|_| |

|_|_ _| | | |_ _|_|

|_|_ _|_| |_|_|_ _|

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

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

Example

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

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

Prog

(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
(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

Crossrefs

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

Cf. A000045, A000129.

Sequence in context: A330718 A284108 A366939 * A066947 A031011 A271625

Adjacent sequences: A335744 A335745 A335746 * A335748 A335749 A335750

Keyword

nonn

Author

Greg Dresden and Oluwatobi Jemima Alabi, Jun 20 2020

Status

approved