A219867 Number of tilings of a 3 X n rectangle using dominoes and straight (3 X 1) trominoes.

1, 1, 4, 14, 41, 143, 472, 1562, 5233, 17395, 58002, 193346, 644219, 2147421, 7156704, 23852324, 79497767, 264952955, 883057354, 2943113598, 9809007073, 32692164351, 108958689984, 363145140266, 1210315480391, 4033823637937, 13444208923518, 44807796457932

Offset: 0

Author

Alois P. Heinz, Nov 30 2012

Keywords

• nonn
• easy

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,5,12,-3,-11,-30,-5,-13,24,14,24,-3,3,-10,-5,-4,-1,-1).

Crossrefs

Column k=3 of A219866.

Programs

Maple

gf:= -(x^15 +x^13 +x^12 +6*x^11 -x^10 +3*x^9 -10*x^8 -4*x^7 -9*x^6 +2*x^5 +2*x^4 +7*x^3 +2*x^2 -1) / (x^18 +x^17 +4*x^16 +5*x^15 +10*x^14 -3*x^13 +3*x^12 -24*x^11 -14*x^10 -24*x^9 +13*x^8 +5*x^7 +30*x^6 +11*x^5 +3*x^4 -12*x^3 -5*x^2 -x +1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);

Formula

G.f.: see Maple program.