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

Author

Alois P. Heinz, Mar 09 2016

Keywords

• nonn
• easy

Examples

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

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

Crossrefs

Column k=2 of A270061.

Programs

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

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