cp's OEIS Frontend

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

%I A335747 #33 Jun 15 2022 01:51:50
%S A335747 1,3,13,26,66,154,380,904,2204,5286,12818,30854,74636,179948,434820,
%T A335747 1049122,2533818,6115538,14766868,35646080,86064196,207766110,
%U A335747 501609946,1210964110,2923573588,7058053972,17039774268
%N A335747 Number of ways to tile vertically-fault-free 3 X n strip with squares and dominoes.
%C A335747 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:
%C A335747 ._ _ _ _     _ _ _ _
%C A335747 |_ _|_ _|   |_ _|_| |
%C A335747 |_|_ _| |   | |_ _|_|
%C A335747 |_|_ _|_|   |_|_|_ _|
%H A335747 G. C. Greubel, <a href="/A335747/b335747.txt">Table of n, a(n) for n = 0..1000</a>
%H A335747 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,4,-1,-1).
%F A335747 a(n) = a(n-1) + 4*a(n-2) - a(n-3) - a(n-4) for n >= 7.
%F A335747 a(n) = 2*A291227(n) - 8*A112577(n-2) + 2*A112577(n-4) for n >= 4.
%F A335747 a(n) = (2/3)*(A221174(n+1) + (-1)^n*A000045(n-1)) for n >= 3. - _Greg Dresden_, Jul 03 2020
%F A335747 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
%F A335747 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
%e A335747 a(2) = 13 thanks to these thirteen vertically-fault-free tilings of a 3 X 2 strip:
%e A335747 ._ _     _ _     _ _     _ _     _ _     _ _     _ _
%e A335747 |_ _|   |_|_|   |_|_|   |_ _|   |_|_|   |_ _|   |_ _|
%e A335747 |_|_|   |_ _|   |_|_|   |_ _|   |_ _|   |_|_|   |_ _|
%e A335747 |_|_|   |_|_|   |_ _|   |_|_|   |_ _|   |_ _|   |_ _|
%e A335747 ._ _     _ _     _ _     _ _     _ _     _ _
%e A335747 |_ _|   |_ _|   |_ _|   | |_|   |_| |   | | |
%e A335747 | |_|   |_| |   | | |   |_|_|   |_|_|   |_|_|
%e A335747 |_|_|   |_|_|   |_|_|   |_ _|   |_ _|   |_ _|
%t A335747 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 *)
%t A335747 LinearRecurrence[{1,4,-1,-1}, {1,3,13,26,66,154,380}, 40] (* _G. C. Greubel_, Jan 15 2022 *)
%o A335747 (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
%o A335747 (Sage)
%o A335747 def P(n): return lucas_number1(n,2,-1)
%o A335747 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))
%o A335747 [A335747(n) for n in (0..40)] # _G. C. Greubel_, Jan 15 2022
%Y A335747 Cf. A033506 (which gives all tilings of 3 X n strip), A112577, A134438, A291227.
%Y A335747 Cf. A000045, A000129.
%K A335747 nonn
%O A335747 0,2
%A A335747 _Greg Dresden_ and _Oluwatobi Jemima Alabi_, Jun 20 2020