cp's OEIS Frontend

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

%I A164387 #49 May 17 2021 08:49:01
%S A164387 1,2,4,8,14,25,45,82,149,270,489,886,1606,2911,5276,9562,17330,31409,
%T A164387 56926,103173,186991,338903,614229,1113231,2017624,3656749,6627505,
%U A164387 12011714,21770074,39456161,71510489,129605869,234898146,425730250,771595046,1398441654
%N A164387 Number of binary strings of length n with no substrings equal to 0000 or 0010.
%C A164387 Also, number of subsets of {1,...,n} not containing {a,a+1,a+3} for any a.  Also, the number of subsets of {1,...,n} not containing {a,a+2,a+3} for any a. - _David Nacin_, Mar 07 2012
%H A164387 N. J. A. Sloane, <a href="/A164387/b164387.txt">Table of n, a(n) for n = 0..1000</a> [Replaces R. H. Hardin's b-file of 500 terms]
%H A164387 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,1,1).
%F A164387 From _N. J. A. Sloane_, Mar 31 2011: (Start)
%F A164387 For n >= 5, a(n) = a(n-1) + a(n-2) + a(n-4) + a(n-5).
%F A164387 G.f.: (1 + x + x^2 + 2*x^3 + x^4)/(1 - x - x^2 - x^4 - x^5). (End)
%e A164387 When n=5, the bitstrings containing 0000 or 0010 are 00000, 10000, 00001, 10010, 00010, 00100, 00101.  Thus a(5) = 2^5 - 7. - _David Nacin_, Mar 07 2012
%p A164387 f:=proc(n) option remember;
%p A164387 if n <= 3 then 2^n elif n=4 then 14
%p A164387 else f(n-1)+f(n-2)+f(n-4)+f(n-5); fi; end;
%t A164387 LinearRecurrence[{1, 1, 0, 1, 1}, {1, 2, 4, 8, 14}, 40] (* _David Nacin_, Mar 07 2012 *)
%o A164387 (PARI) v=[1,2,4,8,14];while(#v<=1000,v=concat(v,v[#v]+v[#v-1]+v[#v-3]+v[#v-4]));v \\ _Charles R Greathouse IV_, Aug 01 2011
%o A164387 (Python)
%o A164387 def a(n, adict={0:1, 1:2, 2:4, 3:8, 4:14}):
%o A164387     if n in adict:
%o A164387         return adict[n]
%o A164387     adict[n]=a(n-1)+a(n-2)+a(n-4)+a(n-5)
%o A164387     return adict[n] # _David Nacin_, Mar 07 2012
%Y A164387 Cf. A209400.
%K A164387 nonn,easy
%O A164387 0,2
%A A164387 _R. H. Hardin_, Aug 14 2009
%E A164387 Edited by _N. J. A. Sloane_, Mar 31 2011