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

Author

Greg Dresden and Saim Usmani, Jul 05 2025

Keywords

• nonn
• easy

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

_

||

|||______________

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

|||

|_|

Examples

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

Links

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

Crossrefs

Cf. A000930, A179070.

Programs

Mathematica

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

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