A165791 Number of tilings of a 4 X n rectangle using dominoes and right trominoes.

1, 1, 11, 55, 380, 2319, 15171, 96139, 619773, 3962734, 25445515, 163048957, 1045897075, 6705473761, 43001795070, 275730928993, 1768128097215, 11337760387473, 72702310606249, 466192677008538, 2989403530821497, 19169143325987983, 122919655766448729

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..400

Index entries for linear recurrences with constant coefficients, signature (4, 21, -25, -65, -17, 24, -11, -15, 9).

Formula

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

Example

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

Maple

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

Mathematica

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

Crossrefs

Cf. A165716, A127870, A054854, A226322.

Column k=4 of A219987.

Sequence in context: A098992 A246990 A156589 * A032166 A218000 A206528

Adjacent sequences: A165788 A165789 A165790 * A165792 A165793 A165794

Keyword

easy,nice,nonn

Author

Alois P. Heinz, Sep 26 2009

Status

approved