OFFSET
0,4
COMMENTS
a(n) is the number of ways to tile a zig-zag strip of n cells using squares (of 1 cell) and strips and triangles (of 3 cells). Here is the zig-zag strip corresponding to n=11, with 11 cells:
___ ___
___| |___| |___
| |___| |___| |___
|___| |___| |___| |
| |___| |___| |___|
|___| |___| |___|,
and here are the strip and triangle of 3 cells (which can be reflected):
___ ___
___| | | |___
___| ___| | |
| ___| | ___|
|___| |___|.
As an example, here is one of the a(11) = 78 ways to tile the zig-zag strip of 11 cells:
___ ___
___| |___| |___
| |___| | |___
|___| ___| ___| |
| ___| |___| |___|
|___| |___| |___|.
LINKS
Index entries for linear recurrences with constant coefficients, signature (0,1,0,4,0,0,0,-2,0,-1).
FORMULA
a(n) = a(n-2) + 4*a(n-4) - 2*a(n-8) - a(n-10).
a(2*n) = a(2*n-1) + a(2*n-2) - a(2*n-3) + a(2*n-4).
a(2*n+1) = a(2*n) + a(2*n-2) +2*a(2*n-3) - a(2*n-4) - a(2*n-7).
G.f.: (x^8-x^5-2*x^4+x^3+x+1)/(x^10+2*x^8-4*x^4-x^2+1).
MATHEMATICA
LinearRecurrence[{0, 1, 0, 4, 0, 0, 0, -2, 0, -1}, {1, 1, 1, 2, 3, 5, 7, 13, 18, 31}, 40]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Greg Dresden and Ziyi Xie, Oct 01 2023
STATUS
approved