login
A368430
Number of binary words of length n not containing the substrings 0000, 0001, 0011, 0111.
2
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
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 *)
LinearRecurrence[{1, 1, 1, -2}, {1, 2, 4, 8}, 50] (* Paolo Xausa, Jun 24 2024 *)
CROSSREFS
Sequence in context: A307732 A103258 A100684 * A131770 A322419 A246850
KEYWORD
nonn,easy
AUTHOR
Miquel A. Fiol, Dec 24 2023
STATUS
approved