A365967 a(2*n) = A030186(n), a(2*n+1) = A033505(n).

1, 1, 2, 3, 7, 10, 22, 32, 71, 103, 228, 331, 733, 1064, 2356, 3420, 7573, 10993, 24342, 35335, 78243, 113578, 251498, 365076, 808395, 1173471, 2598440, 3771911, 8352217, 12124128, 26846696, 38970824, 86293865, 125264689, 277376074, 402640763, 891575391

Offset

0,3

Comments

a(n) is the number of ways to tile a double-height board of n cells with squares and dominos. For example, here is the board for n=9:

_______

|_|_|_|_|_

|_|_|_|_|_|

and here is one of the a(9)=103 possible tilings of this board:

_______

| |_|_|_|_

|_|_|___|_|.

Links

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

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

Formula

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

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

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

Mathematica

a[0] = 1; a[1] = 1; a[2] = 2; a[3] = 3;
a[n_] := a[n] = If[EvenQ[n], a[n-1] + a[n-2] + a[n-3] + a[n-4], a[n-1] + a[n-2]];
Table[a[n], {n, 0, 30}]

Crossrefs

Cf. A030186, A033505.

Sequence in context: A306008 A291241 A318406 * A079380 A263402 A047082

Adjacent sequences: A365964 A365965 A365966 * A365968 A365969 A365970

Keyword

nonn,easy

Author

Greg Dresden, Sep 23 2023

Status

approved