

A000253


a(n) = 2*a(n1)  a(n2) + a(n3) + 2^(n1).


2



0, 1, 4, 11, 27, 63, 142, 312, 673, 1432, 3015, 6295, 13055, 26926, 55284, 113081, 230572, 468883, 951347, 1926527, 3894878, 7863152, 15855105, 31936240, 64269135, 129234351, 259690239, 521524126, 1046810092, 2100221753, 4212028452, 8444387067
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

From Holger Petersen (petersen(AT)informatik.unistuttgart.de), May 29 2006: (Start)
Also number of binary strings of length n+2 containing the pattern 010. Proof: Clear for n = 0, 1, 2. For n > 2 each string with pattern 010 of length n1 gives 2 strings of length n with the property by appending a symbol. In addition each string of length n1 without 010 and ending in 01 contributes one new string. Denote by c_w(m) the number of strings of length m without 010 and ending in w.
Since there is a total of 2^m strings of length m, we have c_01(m) = c_0(m1) = (2^{m1}  a(m3))  c_1(m1) = (2^{m1}  a(m3))  (2^{m2}  a(m4)) = 2^{m2}  a(m3) + a(m4) (the first and third equalities follow from the fact that appending a 1 will not generate the pattern). The recurrence is a(n) = 2a(n1) + c_01(n+1) = 2a(n1) + 2^{n1}  a(n2) + a(n3).
(End)


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Stack Exchange, Recurrence relations  binary substrings
Index to sequences with linear recurrences with constant coefficients, signature (4,5,3,2).


FORMULA

a(n) = (1/3) *(4*2^n + A077941(n1)  2*A077941(n+1)). G.f.: x/((12*x)*(12*x+x^2x^3)).  Ralf Stephan, Aug 19 2004
a(n) = A000079(n+2)  A005251(n+5). Alois P. Heinz, Apr 03 2012


MAPLE

f := proc(n) option remember; if n<=1 then n else if n<=3 then 7*n10; else 2*f(n1)f(n2)+f(n3)+2^(n1); fi; fi; end;


MATHEMATICA

nn=50; a=x^2/(1x)^2; Drop[CoefficientList[Series[a x/(1a x)/(12x), {x, 0, nn}], x], 2] (* Geoffrey Critzer, Nov 26 2013 *)


CROSSREFS

Sequence in context: A119706 A034345 A036890 * A047859 A100335 A080869
Adjacent sequences: A000250 A000251 A000252 * A000254 A000255 A000256


KEYWORD

nonn


AUTHOR

Jason Howald (jahowald(AT)umich.edu)


STATUS

approved



