|
%I #47 Aug 12 2022 20:01:55
%S 0,1,4,11,27,63,142,312,673,1432,3015,6295,13055,26926,55284,113081,
%T 230572,468883,951347,1926527,3894878,7863152,15855105,31936240,
%U 64269135,129234351,259690239,521524126,1046810092,2100221753,4212028452,8444387067
%N a(n) = 2*a(n-1) - a(n-2) + a(n-3) + 2^(n-1).
%C From Holger Petersen (petersen(AT)informatik.uni-stuttgart.de), May 29 2006: (Start)
%C 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 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).
%C (End)
%H Alois P. Heinz, <a href="/A000253/b000253.txt">Table of n, a(n) for n = 0..1000</a>
%H Mathematics Stack Exchange, <a href="http://math.stackexchange.com/questions/86495">Recurrence relations - binary substrings</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,3,-2).
%F From _Ralf Stephan_, Aug 19 2004: (Start)
%F a(n) = (1/3)*(4*2^n + A077941(n-1) - 2*A077941(n+1)).
%F G.f.: x/((1-2*x)*(1 - 2*x + x^2 - x^3)). (End)
%F a(n) = A000079(n+2) - A005251(n+5). - _Alois P. Heinz_, Apr 03 2012
%p 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;
%p # second Maple program:
%p a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-2|3|-5|4>>^n)[3, 4]:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Mar 27 2017
%t nn=50; a=x^2/(1-x)^2; Drop[CoefficientList[Series[a x/(1-a x)/(1-2x), {x,0,nn}], x], 2] (* _Geoffrey Critzer_, Nov 26 2013 *)
%t LinearRecurrence[{4, -5, 3, -2}, {0, 1, 4, 11}, 32] (* _Jean-François Alcover_, Feb 06 2016 *)
%K nonn
%O 0,3
%A Jason Howald (jahowald(AT)umich.edu)
|
