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

Author

Greg Dresden, Sep 23 2023

Keywords

• nonn
• easy

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

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

Crossrefs

Cf. A030186, A033505.

Programs

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}]

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