login
Number of tilings of a 3 X n rectangle using dominoes and right trominoes.
9

%I #23 Nov 15 2021 12:16:44

%S 1,0,5,8,55,140,633,1984,7827,26676,99621,351080,1283247,4583580,

%T 16611505,59652624,215457835,775371268,2796772765,10073343672,

%U 36315180295,130843331180,471599612393,1699398816608,6124635653443,22071172760532,79541846573973

%N Number of tilings of a 3 X n rectangle using dominoes and right trominoes.

%H Alois P. Heinz, <a href="/A165716/b165716.txt">Table of n, a(n) for n = 0..550</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,6,-4,11,2).

%F G.f.: (2*x^4 - 2*x^3 + x^2 + 2*x - 1) / (2*x^5 + 11*x^4 - 4*x^3 + 6*x^2 + 2*x - 1).

%F a(0)=1, a(1)=0, a(2)=5, a(3)=8, a(4)=55, a(n) = 2*a(n-1) + 6*a(n-2) - 4*a(n-3) + 11*a(n-4) + 2*a(n-5). - _Harvey P. Dale_, Mar 19 2013

%e a(2) = 5, because there are 5 tilings of a 3 X 2 rectangle using dominoes and right trominoes:

%e .___. .___. ._._. .___. .___.

%e |___| |_._| | | | | ._| |_. |

%e |___| | | | |_|_| |_| | | |_|

%e |___| |_|_| |___| |___| |___|

%p a:= n-> (Matrix([[55, 8, 5, 0, 1]]). Matrix(5, (i,j)-> if i=j-1 then 1 elif j=1 then [2, 6, -4, 11, 2][i] else 0 fi)^n)[1,5]: seq(a(n), n=0..25);

%t a[n_] := Last[{55, 8, 5, 0, 1} . MatrixPower[ Table[ Which[i == j - 1, 1, j == 1, {2, 6, -4, 11, 2}[[i]], True, 0], {i, 1, 5}, {j, 1, 5}], n]]; Table[a[n], {n, 0, 24}] (* _Jean-François Alcover_, Jul 19 2012, translated from Maple *)

%t LinearRecurrence[{2,6,-4,11,2},{1,0,5,8,55},30] (* _Harvey P. Dale_, Mar 19 2013 *)

%Y Column k=3 of A219987.

%K easy,nice,nonn

%O 0,3

%A _Alois P. Heinz_, Sep 24 2009