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
Examples
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.
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).
Programs
-
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 *)
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