The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000253 a(n) = 2*a(n-1) - a(n-2) + a(n-3) + 2^(n-1). 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.uni-stuttgart.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 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. 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). (End) LINKS Alois P. Heinz, Table of n, a(n) for n = 0..1000 Maths Stack Exchange, Recurrence relations - binary substrings Index entries for linear recurrences with constant coefficients, signature (4,-5,3,-2). FORMULA a(n) = (1/3) *(4*2^n + A077941(n-1) - 2*A077941(n+1)). G.f.: x/((1-2*x)*(1-2*x+x^2-x^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*n-10; else 2*f(n-1)-f(n-2)+f(n-3)+2^(n-1); fi; fi; end; # second Maple program: a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-2|3|-5|4>>^n)[3, 4]: seq(a(n), n=0..30);  # Alois P. Heinz, Mar 27 2017 MATHEMATICA 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 *) LinearRecurrence[{4, -5, 3, -2}, {0, 1, 4, 11}, 32] (* Jean-François Alcover, Feb 06 2016 *) CROSSREFS Sequence in context: A119706 A034345 A036890 * A276691 A047859 A100335 Adjacent sequences:  A000250 A000251 A000252 * A000254 A000255 A000256 KEYWORD nonn AUTHOR Jason Howald (jahowald(AT)umich.edu) STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 29 16:43 EDT 2020. Contains 334704 sequences. (Running on oeis4.)