%I #17 Aug 19 2024 08:33:58
%S 1,1,11,55,380,2319,15171,96139,619773,3962734,25445515,163048957,
%T 1045897075,6705473761,43001795070,275730928993,1768128097215,
%U 11337760387473,72702310606249,466192677008538,2989403530821497,19169143325987983,122919655766448729
%N Number of tilings of a 4 X n rectangle using dominoes and right trominoes.
%H Alois P. Heinz, <a href="/A165791/b165791.txt">Table of n, a(n) for n = 0..400</a>
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (4, 21, -25, -65, -17, 24, -11, -15, 9).
%F G.f.: (2*x^8-5*x^7+2*x^6-x^5-19*x^4-15*x^3+14*x^2+3*x-1) / (9*x^9-15*x^8-11*x^7+24*x^6-17*x^5-65*x^4-25*x^3+21*x^2+4*x-1).
%e a(2) = 11, because there are 11 tilings of a 4 X 2 rectangle using dominoes and right trominoes:
%e .___. .___. .___. ._._. ._._. .___. .___. .___. .___. .___. .___.
%e |___| |___| |_._| | | | | | | |___| |___| | ._| |_. | | ._| |_. |
%e |___| |_._| | | | |_|_| |_|_| | ._| |_. | |_| | | |_| |_| | | |_|
%e |___| | | | |_|_| |___| | | | |_| | | |_| |___| |___| | |_| |_| |
%e |___| |_|_| |___| |___| |_|_| |___| |___| |___| |___| |___| |___| .
%p a:= n-> (Matrix([[619773, 96139, 15171, 2319, 380, 55, 11, 1, 1]]). Matrix(9, (i,j)-> if i=j-1 then 1 elif j=1 then [4, 21, -25, -65, -17, 24, -11, -15, 9][i] else 0 fi)^n)[1,9]: seq(a(n), n=0..25);
%t a[n_] := {619773, 96139, 15171, 2319, 380, 55, 11, 1, 1} . MatrixPower[ Table[ Which[i == j-1, 1, j == 1, {4, 21, -25, -65, -17, 24, -11, -15, 9}[[i]], True, 0], {i, 1, 9}, {j, 1, 9}], n] // Last; Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Dec 04 2013, translated and adapted from _Alois P. Heinz_'s Maple program *)
%Y Cf. A165716, A127870, A054854, A226322.
%Y Column k=4 of A219987.
%K easy,nice,nonn
%O 0,3
%A _Alois P. Heinz_, Sep 26 2009