A164438 Number of binary strings of length n with no substrings equal to 0000 0110 or 0111.

13, 21, 32, 49, 73, 109, 161, 238, 350, 515, 756, 1110, 1628, 2388, 3501, 5133, 7524, 11029, 16165, 23693, 34725, 50894, 74590, 109319, 160216, 234810, 344132, 504352, 739165, 1083301, 1587656, 2326825, 3410129, 4997789, 7324617, 10734750

Offset

4,1

Links

R. H. Hardin, Table of n, a(n) for n = 4..500

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

Formula

G.f.: -x^4*(-13-8*x+2*x^2+4*x^3+8*x^4) / ( (x-1)*(1+x)*(x^3+x-1) ). - R. J. Mathar, Jan 19 2011

Prog

(PARI) a(n)=([0, 1, 0, 0, 0; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0, 1; -1, 0, 0, 1, 1]^(n-4)*[13; 21; 32; 49; 73])[1, 1] \\ Charles R Greathouse IV, Jun 05 2026

Crossrefs

Sequence in context: A164458 A164452 A164444 * A164490 A164460 A164448

Adjacent sequences: A164435 A164436 A164437 * A164439 A164440 A164441

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Status

approved