A340217 - OEIS

A340217

Consider binary words that begin with 1 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, 2, 4, 7, 12, 20, 34, 58, 99, 169, 288, 491, 837, 1427, 2433, 4148, 7072, 12057, 20556, 35046, 59750, 101868, 173675, 296099, 504820, 860669, 1467357, 2501701, 4265157, 7271678, 12397504, 21136539, 36035744, 61437440, 104744862, 178579806, 304461207, 519076757, 884975404, 1508797023

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

a(n) and A340215 follow the same Fibonacci-like recursion with different initial conditions.

a(n+1) is the total number of binary words of length n described in Name (starting with either 0 or 1). For n = 0, a(1) = 1 counts the empty word.

LINKS

Table of n, a(n) for n=1..40.

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

FORMULA

a(n) = a(n-1) + a(n-2) + a(n-5) with a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 7, a(5) = 12.

G.f.: x*(1 + x + x^2 + x^3 + x^4)/(1 - x - x^2 - x^5). - Stefano Spezia, Jan 01 2021

EXAMPLE

a(5)=12: 10011, 10100, 10101, 10110, 10111, 11001, 11010, 11011, 11100, 11101, 11110, 11111. Note 10011 gets counted at n=5 and 100111 at n=6. Similarly, 11001 gets counted at n=5, 110011 at n=6, and 1100111 at n=7.

CROSSREFS

Cf. A164477.

Sequence in context: A172524 A094925 A289168 * A289000 A289028 A186537

Adjacent sequences: A340214 A340215 A340216 * A340218 A340219 A340220

KEYWORD

nonn,easy

AUTHOR

Enrique Navarrete, Jan 01 2021

STATUS

approved