A365274 a(n) = a(n-2) + 4*a(n-4) - 2*a(n-8) - a(n-10), with a[0..9] = [1, 1, 1, 2, 3, 5, 7, 13, 18, 31].

1, 1, 1, 2, 3, 5, 7, 13, 18, 31, 43, 78, 108, 190, 263, 471, 652, 1156, 1600, 2853, 3949, 7019, 9715, 17299, 23944, 42592, 58952, 104926, 145230, 258403, 357659, 636490, 880976, 1567619, 2169764, 3861135, 5344256, 9509879, 13162764, 23423036, 32420177

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

Table of n, a(n) for n=0..40.

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

Cf. A135318, A366143.

Sequence in context: A342244 A076047 A245640 * A178766 A362778 A362779

Adjacent sequences: A365271 A365272 A365273 * A365275 A365276 A365277

Keyword

nonn,easy

Author

Greg Dresden and Ziyi Xie, Oct 01 2023

Status

approved