|
|
A164413
|
|
Number of binary strings of length n with no substrings equal to 0000, 0001 or 1001.
|
|
1
|
|
|
1, 2, 4, 8, 13, 22, 36, 58, 94, 152, 246, 398, 644, 1042, 1686, 2728, 4414, 7142, 11556, 18698, 30254, 48952, 79206, 128158, 207364, 335522, 542886, 878408, 1421294, 2299702, 3720996, 6020698, 9741694, 15762392, 25504086, 41266478, 66770564, 108037042
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
G.f.: -(x^2+1)*(x^2-x+1)*(x+1)^2/(x^2+x-1).
a(n) = 2*(((1 - sqrt(5))/2)^n + ((1 + sqrt(5))/2)^n) for n>4.
a(n) = a(n-1) + a(n-2) for n>6.
(End)
|
|
PROG
|
(PARI) Vec(-(x^2+1)*(x^2-x+1)*(x+1)^2/(x^2+x-1) + O(x^50)) \\ Colin Barker, Oct 27 2017
(PARI) first(n) = {my(start = [1, 2, 4, 8, 13, 22, 36]); if(n <= 7, return(vector(n+1, i, start[i]))); res = concat(start, vector(n-7)); for(i=8, n,
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|