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,2

Links

Paolo Xausa, Table of n, a(n) for n = 0..1000

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

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

Mathematica

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

Crossrefs

Cf. A052947, A164395, A164408, A368430.

Sequence in context: A053439 A337501 A365922 * A180379 A033956 A282620

Adjacent sequences: A373077 A373078 A373079 * A373081 A373082 A373083

Keyword

nonn,easy

Author

Miquel A. Fiol, Jun 03 2024

Status

approved