login
A340215
Consider constructing binary words that begin with 0 such that the subword 00, whenever it appears, is followed by 111. Then a(n) counts such words at length n (including those where the string 111 is yet being completed - see Example).
1
1, 2, 3, 5, 8, 14, 24, 41, 70, 119, 203, 346, 590, 1006, 1715, 2924, 4985, 8499, 14490, 24704, 42118, 71807, 122424, 208721, 355849, 606688, 1034344, 1763456, 3006521, 5125826, 8739035, 14899205, 25401696, 43307422, 73834944, 125881401, 214615550, 365898647, 623821619, 1063555210, 1813258230
OFFSET
1,2
COMMENTS
a(n) follows the Fibonacci recursion with an additional term (see Formula).
FORMULA
a(n) = a(n-1) + a(n-2) + a(n-5) with a(1) = 1, a(2) = 2, a(3) = 3, a(4) = 5, a(5) = 8.
G.f.: x*(1 + x)/(1 - x - x^2 - x^5). - Stefano Spezia, Jan 01 2021
EXAMPLE
a(5)=8: 00111, 01001, 01010, 01011, 01100, 01101, 01110, 01111. Note 01001 gets counted at n=5, 010011 at n=6, and 0100111 at n=7.
CROSSREFS
Sequence in context: A316474 A086661 A018154 * A114831 A343161 A274110
KEYWORD
nonn,easy
AUTHOR
Enrique Navarrete, Dec 31 2020
STATUS
approved