A373080 a(n) is the number of binary strings of length n not containing the substrings 0000, 0001, 0011, 0111, 1111.

1, 2, 4, 8, 11, 18, 28, 40, 64, 96, 144, 224, 336, 512, 784, 1184, 1808, 2752, 4176, 6368, 9680, 14720, 22416, 34080, 51856, 78912, 120016, 182624, 277840, 422656, 643088, 978336, 1488400, 2264512, 3445072, 5241312, 7974096, 12131456, 18456720, 28079648

Offset: 0

Author

Miquel A. Fiol, Jun 03 2024

Keywords

• nonn
• easy

Links

• Paolo Xausa, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (0,1,2).

Crossrefs

Cf. A052947, A164395, A164408, A368430.

Programs

Mathematica

LinearRecurrence[{0, 1, 2}, {1, 2, 4, 8, 11, 18, 28}, 50] (* Paolo Xausa, Jun 24 2024 *)

Formula

a(n) = a(n-2) + 2*a(n-3) for n >= 7.

G.f.: -(x+1)^2*(x^2+1)^2/(2*x^3+x^2-1). - Alois P. Heinz, Jun 03 2024