A165799 Number of tilings of a 4 X n rectangle using right trominoes and 2 X 2 tiles.

1, 0, 1, 4, 6, 16, 37, 92, 245, 560, 1426, 3720, 9069, 22808, 58177, 145660, 366318, 925536, 2331269, 5872212, 14802941, 37311528, 94038250, 236999064, 597348237, 1505640016, 3794761257, 9564393972, 24106951622, 60759989040, 153141435269, 385986293964

Offset

0,4

Links

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

Index entries for linear recurrences with constant coefficients, signature (1,1,9,1,-3,-22,-16,0,-4).

Formula

G.f.: -(6*x^3+x-1) / (4*x^9+16*x^7+22*x^6+3*x^5-x^4-9*x^3-x^2-x+1).

a(n) = a(n-1) +a(n-2) +9*a(n-3) +a(n-4) -3*a(n-5) -22*a(n-6) -16*a(n-7) -4*a(n-9).

Example

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

Maple

a:= n-> (Matrix([[4, 1, 0, 1, 0$5]]). Matrix(9, (i, j)-> if i=j-1 then 1 elif j=1 then [1, 1, 9, 1, -3, -22, -16, 0, -4][i] else 0 fi)^n)[1, 4]: seq(a(n), n=0..30);

Mathematica

Series[ (-6*x^3 - x + 1) / (4*x^9 + 16*x^7 + 22*x^6 + 3*x^5 - x^4 - 9*x^3 - x^2 - x + 1), {x, 0, 31}] // CoefficientList[#, x] & (* Jean-François Alcover, Jun 18 2013, after Alois P. Heinz *)
LinearRecurrence[{1, 1, 9, 1, -3, -22, -16, 0, -4}, {1, 0, 1, 4, 6, 16, 37, 92, 245}, 40] (* Harvey P. Dale, Nov 09 2024 *)

Crossrefs

Cf. A165791, A165716, A054854, A054856, A226322.

Column k=4 of A219946.

Sequence in context: A188466 A076066 A227178 * A231998 A056421 A032295

Adjacent sequences: A165796 A165797 A165798 * A165800 A165801 A165802

Keyword

easy,nice,nonn

Author

Alois P. Heinz, Sep 27 2009

Status

approved