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,3

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

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

Example

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

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

Crossrefs

Column k=4 of A220122. Cf. A005178.

Sequence in context: A173809 A298355 A023147 * A220125 A095742 A011951

Adjacent sequences: A220120 A220121 A220122 * A220124 A220125 A220126

Keyword

nonn,easy

Author

Alois P. Heinz, Dec 05 2012

Status

approved