A363958 Expansion of (1 + x + x^3)/(1 - x^2 - 2*x^4 - 2*x^6 + x^8).

1, 1, 1, 2, 3, 4, 7, 10, 16, 23, 37, 53, 86, 123, 199, 285, 461, 660, 1068, 1529, 2474, 3542, 5731, 8205, 13276, 19007, 30754, 44030, 71242, 101996, 165033, 236275, 382301, 547334, 885605, 1267906, 2051515, 2937120

Offset

0,4

Comments

a(n) is the number of ways to tile a zig-zag strip of n cells using squares (of length 1), strips (of length 3), and triangles (using 3 cells), where the zig-zag strip begins below the center line. Here is the zig-zag strip corresponding to n=12, with 12 cells:

___ ___ ___

| | | | | |

_|_ _|_ _|_ _|_ _|_ _|_

| | | | | | |

_|___|___|___|___|_ _|___|

| | | | | |

|___| |___| |___|,

and here are the three possible triangles and strips (which can also be rotated or reflected):

___

| |

_| _| ___

| | | |

_| __| ___ ___ ___ _| |_

| | | | | |

|___|, |___ ___ ___|, |___ ___|.

As an example, here is one of the a(12) = 86 ways to tile the skew double-strip of 12 cells:

___ ___ ___

| | | | | |

_| _|___|_ _|___|___|_

| | | |

_| __|_ _|___________|

| | | | | |

|___| |___| |___|.

Links

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

Index entries for linear recurrences with constant coefficients, signature (0,1,0,2,0,2,0,1).

Formula

a(n) = a(n-2) + 2*a(n-4) + 2*a(n-6) + a(n-8).

a(2*n) = a(2*n-1) + a(2*n-3) + a(2*n-5).

a(2*n) = A123392(n).

a(2*n+1) = a(2*n) + a(2*n-2).

a(2*n+1) = A210460(n+1).

Mathematica

LinearRecurrence[{0, 1, 0, 2, 0, 2, 0, 1}, {1, 1, 1, 2, 3, 4, 7, 10}, 50]

Crossrefs

Cf. A077998. Alternate terms are A123392 and A210460.

Sequence in context: A319437 A270659 A159288 * A033320 A013982 A202411

Adjacent sequences: A363955 A363956 A363957 * A363959 A363960 A363961

Keyword

nonn,easy

Author

Greg Dresden and Yunxin Li, Jun 29 2023

Status

approved