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,3

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

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

Example

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

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

Crossrefs

Column k=3 of A219987.

Sequence in context: A294665 A323139 A284381 * A068478 A342195 A132050

Adjacent sequences: A165713 A165714 A165715 * A165717 A165718 A165719

Keyword

easy,nice,nonn

Author

Alois P. Heinz, Sep 24 2009

Status

approved