%I #29 Nov 09 2024 10:55:38
%S 1,0,1,4,6,16,37,92,245,560,1426,3720,9069,22808,58177,145660,366318,
%T 925536,2331269,5872212,14802941,37311528,94038250,236999064,
%U 597348237,1505640016,3794761257,9564393972,24106951622,60759989040,153141435269,385986293964
%N Number of tilings of a 4 X n rectangle using right trominoes and 2 X 2 tiles.
%H Alois P. Heinz, <a href="/A165799/b165799.txt">Table of n, a(n) for n = 0..1000</a>
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,9,1,-3,-22,-16,0,-4).
%F G.f.: -(6*x^3+x-1) / (4*x^9+16*x^7+22*x^6+3*x^5-x^4-9*x^3-x^2-x+1).
%F a(n) = a(n-1) +a(n-2) +9*a(n-3) +a(n-4) -3*a(n-5) -22*a(n-6) -16*a(n-7) -4*a(n-9).
%e a(4) = 6, because there are 6 tilings of a 4 X 4 rectangle using right trominoes and 2 X 2 tiles:
%e .___.___. .___.___. .___.___. .___.___. .___.___. .___.___.
%e | . | . | | ._|_. | | ._| . | | ._|_. | | ._|_. | | . |_. |
%e |___|___| |_| . |_| |_| |___| |_| ._|_| |_|_. |_| |___| |_|
%e | . | . | | |___| | | |___| | | |_| . | | . |_| | | |___| |
%e |___|___| |___|___| |___|___| |___|___| |___|___| |___|___|
%p a:= n-> (Matrix([[4, 1, 0, 1, 0$5]]). Matrix(9, (i,j)-> if i=j-1 then 1 elif j=1 then [1, 1, 9, 1, -3, -22, -16, 0, -4][i] else 0 fi)^n)[1,4]: seq(a(n), n=0..30);
%t Series[ (-6*x^3 - x + 1) / (4*x^9 + 16*x^7 + 22*x^6 + 3*x^5 - x^4 - 9*x^3 - x^2 - x + 1), {x, 0, 31}] // CoefficientList[#, x] & (* _Jean-François Alcover_, Jun 18 2013, after _Alois P. Heinz_ *)
%t LinearRecurrence[{1,1,9,1,-3,-22,-16,0,-4},{1,0,1,4,6,16,37,92,245},40] (* _Harvey P. Dale_, Nov 09 2024 *)
%Y Cf. A165791, A165716, A054854, A054856, A226322.
%Y Column k=4 of A219946.
%K easy,nice,nonn,changed
%O 0,4
%A _Alois P. Heinz_, Sep 27 2009