A219968 Number of tilings of a 3 X n rectangle using straight (3 X 1) trominoes and 2 X 2 tiles.

1, 1, 1, 2, 3, 4, 8, 13, 19, 35, 58, 89, 154, 256, 405, 681, 1131, 1822, 3025, 5012, 8156, 13465, 22257, 36415, 59976, 98961, 162370, 267184, 440335, 723521, 1190237, 1960146, 3223045, 5301876, 8727650, 14355677, 23615683, 38865307, 63937660, 105184761

Offset: 0

Author

Alois P. Heinz, Dec 02 2012

Keywords

• nonn
• easy

Examples

			a(6) = 8, because there are 8 tilings of a 3 X 6 rectangle using straight (3 X 1) trominoes and 2 X 2 tiles:
._._._._._._.  ._____._._._.  ._._____._._.  ._._._____._.
| | | | | | |  |_____| | | |  | |_____| | |  | | |_____| |
| | | | | | |  |_____| | | |  | |_____| | |  | | |_____| |
|_|_|_|_|_|_|  |_____|_|_|_|  |_|_____|_|_|  |_|_|_____|_|
._._._._____.  ._____._____.  .___.___.___.  ._____._____.
| | | |_____|  |_____|_____|  |   |   |   |  |_____|_____|
| | | |_____|  |_____|_____|  |___|_._|___|  |   |   |   |
|_|_|_|_____|  |_____|_____|  |_____|_____|  |___|___|___|
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,0,3,-2,0,-1,1,0,1).

Crossrefs

Column k=3 of A219967.

Programs

Maple

gf:= -(x-1)^2*(x^2+x+1)^2 / (x^9+x^7-x^6-2*x^4+3*x^3+x-1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..50);

Formula

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

a(n) = 1 + Sum_{i=0..n-3} a(i)*(1 + B*(B-1)) where B=floor((n-i)/3). E.g. a(7) = 1 + a(0)*3 + a(1)*3 + a(2)*1 + a(3)*1 + a(4)*1 = 13. - Greg Dresden and Andrew Chang, Aug 23 2022