

A164392


Number of binary strings of length n with no substrings equal to 0001 or 0010.


7



1, 2, 4, 8, 14, 25, 44, 78, 137, 241, 423, 743, 1304, 2289, 4017, 7050, 12372, 21712, 38102, 66865, 117340, 205918, 361361, 634145, 1112847, 1952911, 3427120, 6014177, 10554145, 18521234, 32502500, 57037912, 100094558, 175653705, 308250764, 540942382
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Nonnegative walks with n steps on the xaxis starting at the origin using steps {1,0,1} and visiting no point more than twice. Note: a 0 step counts as a visit and a step but does not contribute to the length of the walk.  David Scambler, May 22 2012


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 500 terms from R. H. Hardin)
Index entries for linear recurrences with constant coefficients, signature (2, 0, 1, 1, 1).


FORMULA

From David Scambler, May 22 2012: (Start)
G.f.: (1+x^3x^4)/(12*x+x^3x^4+x^5).
a(n) = 2^n for n<4; otherwise, a(n) = a(n1)+a(n2)+a(n4)+1. (End)


MATHEMATICA

CoefficientList[Series[ (1+x^3x^4)/(12*x+x^3x^4+x^5) , {x, 0, 45}], x] (* David Scambler, May 22 2012 *)


PROG

(PARI) x='x+O('x^50); Vec( (1+x^3x^4)/(12*x+x^3x^4+x^5) ) \\ G. C. Greubel, sep 18 2017


CROSSREFS

Cf. A212584, A212585, A212586, A212587, A212589.
Sequence in context: A164391 A164153 A212588 * A164152 A164390 A164151
Adjacent sequences: A164389 A164390 A164391 * A164393 A164394 A164395


KEYWORD

nonn,easy,walk


AUTHOR

R. H. Hardin, Aug 14 2009


EXTENSIONS

Edited by Alois P. Heinz, Oct 27 2017


STATUS

approved



