cp's OEIS Frontend

A188765 Number of binary strings of length n with no substrings equal to 00000 or 00100.

%I A188765 #35 Jul 07 2017 04:11:37
%S A188765 1,2,4,8,16,30,57,108,207,397,761,1456,2784,5324,10185,19488,37288,
%T A188765 71341,136486,261117,499561,955756,1828549,3498364,6693021,12804983,
%U A188765 24498304,46869822,89670729,171556853,328220258,627946528,1201378750,2298461537,4397385531,8413018547,16095673253,30794024151,58914710037,112714825621,215644478604,412568097507,789319699503,1510115764260
%N A188765 Number of binary strings of length n with no substrings equal to 00000 or 00100.
%C A188765 Thanks to Michael Somos for telling me about Mathematica's SatisfiabilityCount command.
%C A188765 Thanks to Doron Zeilberger for telling me about the Noonan-Zeilberger GJs command.
%H A188765 Vincenzo Librandi, <a href="/A188765/b188765.txt">Table of n, a(n) for n = 0..1000</a>
%H A188765 J. Noonan and D. Zeilberger, <a href="http://arXiv.org/abs/math.CO/9806036">The Goulden-Jackson cluster method: extensions, applications and implementations</a>
%H A188765 Doron Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/gj.html">Webpage of the paper `The Goulden-Jacskon Cluster Method: Extensions, Applications and Implementations', by John Noonan and Doron Zeilberger</a>
%H A188765 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,1,2,2,1)
%F A188765 G.f.: (1 + x + x^2 + 2*x^3 + 3*x^4 + 2*x^5 + x^6) / (1 - x - x^2 - x^4 - 2*x^5 - 2*x^6 - x^7).
%e A188765 1 + 2*x + 4*x^2 + 8*x^3 + 16*x^4 + 30*x^5 + 57*x^6 + 108*x^7 + 207*x^8 + ...
%p A188765 # First download the Maple package DAVID_IAN from the Zeilberger web site
%p A188765 read(DAVID_IAN);
%p A188765 GJs({0,1},{[0,0,0,0,0],[0,0,1,0,0]},x);
%t A188765 a[ n_] := If[ n<0, 0, Length @ Cases[ Tuples[ {0, 1}, n], Except @ {___, 0, 0, _, 0, 0, ___}]] (* _Michael Somos_, Apr 10 2011 *)
%t A188765 SPAN = 5; MMM = 60;
%t A188765 For[ M=SPAN, M <= MMM, M++,
%t A188765 vlist = Array[x, M];
%t A188765 cl[i_] := Or[ x[i], x[i+1], x[i+3], x[i+4] ];
%t A188765 cl2 = True; For [ i=1, i <= M-SPAN+1, i++, cl2 = And[cl2, cl[i]] ];
%t A188765 R[M] = SatisfiabilityCount[ cl2, vlist ] ]
%t A188765 Table[ R[M], {M,SPAN,MMM}] (* _N. J. A. Sloane_ *)
%t A188765 CoefficientList[Series[(1 + x + x^2 + 2 x^3 + 3 x^4 + 2 x^5 + x^6)/(1 - x - x^2 - x^4 - 2 x^5 - 2 x^6 - x^7), {x, 0, 50}], x] (* _Vincenzo Librandi_, Dec 09 2012 *)
%o A188765 (PARI) {a(n) = local(m, k); if( n<0, 0, forvec( v = vector( n, i, [0, 1]), k=0; for( i = 1, n-4, if( [v[i], v[i+1], v[i+3], v[i+4]] == [0, 0, 0, 0], k=1; break)); if( !k, m++)); m)} /* _Michael Somos_, Apr 09 2011 */
%Y A188765 Cf. A164387.
%K A188765 nonn,easy
%O A188765 0,2
%A A188765 _N. J. A. Sloane_, Apr 09 2011