A368430 Number of binary words of length n not containing the substrings 0000, 0001, 0011, 0111.

1, 2, 4, 8, 12, 20, 32, 48, 76, 116, 176, 272, 412, 628, 960, 1456, 2220, 3380, 5136, 7824, 11900, 18100, 27552, 41904, 63756, 97012, 147568, 224528, 341596, 519668, 790656, 1202864, 1829996, 2784180, 4235728, 6444176, 9804092, 14915636, 22692448, 34523824

Offset

0,2

Links

Ray Chandler, Table of n, a(n) for n = 0..1000

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

Formula

a(n) = a(n-1) + a(n-2) + a(n-3) - 2*a(n-4) with a(0)=1, a(1)=2, a(2)=4, and a(3)=8.

G.f.: (x+1)*(x^2+1)/((x-1)*(2*x^3+x^2-1)). - Alois P. Heinz, Dec 30 2023

Example

For n=5, the a(5) = 20 words are: 00100, 00101, 01000, 01001, 01010, 01011, 01100, 01101, 10010, 10100, 10101, 10110, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111.

Mathematica

m={
 {1, 1, 0, 0, 0, 0, 0},
 {0, 0, 1, 1, 0, 0, 0},
 {0, 0, 0, 0, 1, 1, 0},
 {0, 1, 0, 0, 0, 1, 0},
 {0, 0, 0, 0, 0, 0, 2},
 {0, 1, 0, 0, 0, 0, 1},
 {0, 0, 0, 0, 0, 0, 2}
};
a[0] = 1; a[n_]:=(2^n-MatrixPower[m, n][[1, 7]]);
Table[a[n], {n, 1, 39}] (* Robert P. P. McKone, Jan 01 2024 *)

Crossrefs

Cf. A164408.

Sequence in context: A307732 A103258 A100684 * A131770 A322419 A246850

Adjacent sequences: A368427 A368428 A368429 * A368431 A368432 A368433

Keyword

nonn,easy

Author

Miquel A. Fiol, Dec 24 2023

Status

approved