A220123 Number of tilings of a 4 X n rectangle using integer-sided rectangular tiles of area 4.

1, 1, 2, 3, 9, 16, 35, 65, 143, 281, 590, 1174, 2440, 4925, 10142, 20563, 42178, 85819, 175632, 357875, 731536, 1491966, 3047879, 6218844, 12699982, 25919176, 52922491, 108022099, 220541999, 450186874, 919074255, 1876149465, 3830134125, 7818778884, 15961716918

Offset: 0

Author

Alois P. Heinz, Dec 05 2012

Keywords

• nonn
• easy

Examples

			a(3) = 3, because there are 3 tilings of a 4 X 3 rectangle using integer-sided rectangular tiles of area 4:
._._._.   ._.___.   .___._.
| | | |   | |   |   |   | |
| | | |   | |___|   |___| |
| | | |   | |   |   |   | |
|_|_|_|   |_|___|   |___|_|
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Caleb Wagner, Number of tilings of a 4 X n rectangle using integer sided rectangular tiles of area 4, Nov 2013
• Index entries for linear recurrences with constant coefficients, signature (1,1,0,5,-1,1,0,-1).

Crossrefs

Column k=4 of A220122. Cf. A005178.

Programs

Maple

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

Formula

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

a(n) = a(n-1) + a(n-2) + 5*a(n-4) - a(n-5) + a(n-6) - a(n-8). - Caleb Wagner, Nov 06 2013

a(2*n+1) = Sum_{k=0..n} A005178(k+1)*a(2*n-2*k). - Shravan Haribalaraman, Aug 29 2022