A385633 a(n) = a(n-1) + a(n-3), with a(0) = 1, a(1) = 4, a(2) = 8.

1, 4, 8, 9, 13, 21, 30, 43, 64, 94, 137, 201, 295, 432, 633, 928, 1360, 1993, 2921, 4281, 6274, 9195, 13476, 19750, 28945, 42421, 62171, 91116, 133537, 195708, 286824, 420361, 616069, 902893, 1323254, 1939323, 2842216, 4165470, 6104793, 8947009, 13112479, 19217272

Offset

0,2

Comments

a(n) is the number of ways to tile this shape, of length n, with 1 X 1 squares and 1 X 3 rectangles (which can be either horizontal or vertical).

_

|_|_

|_|_|______________

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

|_|_|

|_|

Links

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

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

Formula

a(n) = b(n+4) + 2*b(n-5) for b(n) = A000930(n), Narayana's cows sequence.

G.f.: (1 + 3*x + 4*x^2)/(1 - x - x^3). - Stefano Spezia, Jul 06 2025

Example

Shown here is one of the a(4)=13 ways to tile this shape of length 4:
   _
  | |_
  | | |____
  |_| |_|_|
  |_|_|
  |_|

Mathematica

LinearRecurrence[{1, 0, 1}, {1, 4, 8}, 40]

Crossrefs

Cf. A000930, A179070.

Sequence in context: A010429 A376357 A140282 * A161757 A134376 A163408

Adjacent sequences: A385630 A385631 A385632 * A385634 A385635 A385636

Keyword

nonn,easy

Author

Greg Dresden and Saim Usmani, Jul 05 2025

Status

approved