A164414 Number of binary strings of length n with no substrings equal to 0000, 0001, or 1010.

1, 2, 4, 8, 13, 22, 37, 63, 107, 181, 307, 521, 883, 1497, 2539, 4305, 7299, 12377, 20987, 35585, 60339, 102313, 173483, 294161, 498787, 845753, 1434075, 2431649, 4123155, 6991305, 11854603, 20100913, 34083523, 57792729, 97994555, 166161601, 281747059

Offset: 0

Author

R. H. Hardin, Aug 14 2009

Keywords

• easy
• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2000 (terms n=4..500 from R. H. Hardin)
• Index entries for linear recurrences with constant coefficients, signature (1,0,2).

Crossrefs

Cf. A077949.

Formula

From R. J. Mathar, Nov 30 2011: (Start)

a(n) = 13*A077949(n-4) + 9*A077949(n-5) + 15*A077949(n-6).

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

(End)

Extensions

a(0)-a(3) from Alois P. Heinz, Jun 10 2021