login
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.
0
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:
_
_________|_|_______
|_|_|_|_|_|_|_|_|_|_|
|_|
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
KEYWORD
nonn,easy
AUTHOR
Greg Dresden and Jiaqi Wang, Jun 18 2023
STATUS
approved