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

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);

Mathematica

LinearRecurrence[{1, 1, 0, 0, 0, -2, 0, 1}, {1, 2, 4, 8, 12, 18, 27, 41}, 40] (* Jean-François Alcover, Nov 02 2021 *)

Crossrefs

Cf. A164417, A164420.

Sequence in context: A224814 A224810 A074633 * A006500 A134181 A171645

Adjacent sequences: A294046 A294047 A294048 * A294050 A294051 A294052

Keyword

nonn,easy

Author

Alois P. Heinz, Oct 22 2017

Status

approved