A362388 a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 2, a(2) = 5, a(3) = 7.

1, 2, 5, 7, 10, 17, 29, 46, 73, 119, 194, 313, 505, 818, 1325, 2143, 3466, 5609, 9077, 14686, 23761, 38447, 62210, 100657, 162865, 263522, 426389, 689911, 1116298, 1806209, 2922509, 4728718, 7651225, 12379943, 20031170, 32411113, 52442281, 84853394

Offset

0,2

Comments

For n >= 3, a(n) is also the number of ways to tile this "central staircase" figure of length n with squares and dominoes; this is the picture for length n=10:

_

_________|_|_______

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

|_|

Links

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

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

Formula

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 2, a(2) = 5, a(3) = 7.

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

a(2*n) = F(n+2)^2 + F(n)^2, a(2*n+1) = F(n+2)^2 + F(n+1)*L(n+1) for F(n) and L(n) the Fibonacci and Lucas numbers.

Sum_{k=0..n} a(k) = A295681(n+5) - 3.

5*a(n) = 3*A000032(n+2) -2*A000034(n+1)*(-1)^floor(n/2). - R. J. Mathar, Jun 22 2023

a(n)+a(n+2) = 3*A000045(n+3). - R. J. Mathar, Jun 22 2023

Example

Here is one of the a(10)=194 tilings for length n=10:
             _
   _________|_|_______
  |___|___| |___|_|___|
          |_|

Mathematica

LinearRecurrence[{1, 0, 1, 1}, { 1, 2, 5, 7}, 50]

Crossrefs

Cf. A000032, A000045, A195971, A295681, A347902.

Sequence in context: A345127 A226813 A355846 * A076802 A226650 A024374

Adjacent sequences: A362385 A362386 A362387 * A362389 A362390 A362391

Keyword

nonn,easy

Author

Greg Dresden and Jiaqi Wang, Jun 18 2023

Status

approved