A294049 - OEIS

A294049

Number of binary strings of length n avoiding substrings 1000, 1011, 1101, or 1111.

1, 2, 4, 8, 12, 18, 27, 41, 61, 88, 129, 189, 276, 401, 582, 848, 1233, 1791, 2601, 3779, 5492, 7976, 11584, 16826, 24441, 35500, 51558, 74885, 108767, 157976, 229445, 333247, 484017, 702994, 1021035, 1482962, 2153874, 3128318, 4543603, 6599180, 9584730

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

OFFSET

0,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..2000

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

FORMULA

G.f.: (x+1)*(x^5+x^4-x^3-x^2-1)/((x-1)*(x^7+x^6-x^5-x^4-x^3-x^2+1)).

MAPLE

a:= n-> (Matrix(8, (i, j)-> `if`(i+1=j, 1, `if`(i=8,

[1, 0, -2, 0$3, 1$2][j], 0)))^n. <<1, 2, 4, 8, 12, 18, 27, 41>>)[1$2]:

seq(a(n), n=0..45);