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

1, 0, 5, 8, 55, 140, 633, 1984, 7827, 26676, 99621, 351080, 1283247, 4583580, 16611505, 59652624, 215457835, 775371268, 2796772765, 10073343672, 36315180295, 130843331180, 471599612393, 1699398816608, 6124635653443, 22071172760532, 79541846573973

Offset: 0

Author

Alois P. Heinz, Sep 24 2009

Keywords

• easy
• nice
• nonn

Examples

			a(2) = 5, because there are 5 tilings of a 3 X 2 rectangle using dominoes and right trominoes:
.___. .___. ._._. .___. .___.
|___| |_._| | | | | ._| |_. |
|___| | | | |_|_| |_| | | |_|
|___| |_|_| |___| |___| |___|
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..550
• Index entries for linear recurrences with constant coefficients, signature (2,6,-4,11,2).

Crossrefs

Column k=3 of A219987.

Programs

Maple

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

Mathematica

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 *)
LinearRecurrence[{2,6,-4,11,2},{1,0,5,8,55},30] (* Harvey P. Dale, Mar 19 2013 *)

Formula

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

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