A270062 Number of tilings of a 2 X n rectangle using monominoes and trominoes of any shape.

1, 1, 5, 14, 45, 140, 438, 1371, 4287, 13413, 41956, 131249, 410572, 1284352, 4017713, 12568213, 39315905, 122988066, 384731445, 1203517448, 3764844982, 11777193395, 36841433019, 115247422841, 360517151000, 1127770261265, 3527892525112, 11035958382864

Offset

0,3

Links

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

Wikipedia, Tromino

Index entries for linear recurrences with constant coefficients, signature (1,5,5,1,-1,-1).

Formula

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

a(n) = a(n-1) +5*(a(n-2)+a(n-3)) +a(n-4) -a(n-5) -a(n-6).

Example

a(3) = 14:
._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
|_____|  |_|_|_|  |_____|  |_| |_|  | |_|_|  | ._|_|  |_. |_|
|_____|  |_____|  |_|_|_|  |___|_|  |___|_|  |_|_|_|  |_|_|_|
.
._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
|_|_|_|  | ._| |  | |_. |  |_|_| |  |_| |_|  |_| ._|  |_|_. |
|_|_|_|  |_|___|  |___|_|  |_|___|  |_|___|  |_|_|_|  |_|_|_|  .
.

Maple

a:= n-> (Matrix(6, (i, j)-> `if`(i+1=j, 1, `if`(i=6, [-1$2, 1,
         5$2, 1][j], 0)))^n. <<1, 1, 5, 14, 45, 140>>)[1, 1]:
seq(a(n), n=0..30);

Crossrefs

Column k=2 of A270061.

Sequence in context: A140796 A197212 A100059 * A236043 A270661 A222908

Adjacent sequences: A270059 A270060 A270061 * A270063 A270064 A270065

Keyword

nonn,easy

Author

Alois P. Heinz, Mar 09 2016

Status

approved