%I A000253
%S A000253 0,1,4,11,27,63,142,312,673,1432,3015,6295,13055,26926,55284,
%T A000253 113081,230572,468883,951347,1926527,3894878,7863152,15855105,
%U A000253 31936240,64269135,129234351,259690239,521524126,1046810092
%N A000253 a(n) = 2a(n-1)-a(n-2)+a(n-3)+2^(n-1).
%C A000253 Comment from Holger Petersen (petersen(AT)informatik.uni-stuttgart.de), 
               May 29 2006: "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 n-1 gives 2 strings of length n with the 
               property by appending a symbol. In addition each string of length 
               n-1 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.
%C A000253 "Since there is a total of 2^m strings of length m, we have c_01(m) = 
               c_0(m-1) = (2^{m-1} - a(m-3)) - c_1(m-1) = (2^{m-1} - a(m-3)) - (2^{m-2} 
               - a(m-4)) = 2^{m-2} - a(m-3) + a(m-4) (the first and third equalities 
               follow from the fact that appending a 1 will not generate the pattern). 
               The recurrence is a(n) = 2a(n-1) + c_01(n+1) = 2a(n-1) + 2^{n-1} 
               - a(n-2) + a(n-3)"
%F A000253 a(n) = (1/3) [4*2^n + A077941(n-1) - 2*A077941(n+1)]. G.f.: x/[(1-2x)(1-2x+x^2+x^3)]. 
               - R. Stephan, Aug 19 2004
%p A000253 f := proc(n) option remember; if n<=1 then n else if n<=3 then 7*n-10; 
               else 2*f(n-1)-f(n-2)+f(n-3)+2^(n-1); fi; fi; end;
%Y A000253 Sequence in context: A119706 A034345 A036890 this_sequence A047859 A100335 
               A080869
%Y A000253 Adjacent sequences: A000250 A000251 A000252 this_sequence A000254 A000255 
               A000256
%K A000253 nonn
%O A000253 0,3
%A A000253 Jason Howald (jahowald(AT)umich.edu)