A188765 - OEIS

%I #35 Jul 07 2017 04:11:37

%S 1,2,4,8,16,30,57,108,207,397,761,1456,2784,5324,10185,19488,37288,

%T 71341,136486,261117,499561,955756,1828549,3498364,6693021,12804983,

%U 24498304,46869822,89670729,171556853,328220258,627946528,1201378750,2298461537,4397385531,8413018547,16095673253,30794024151,58914710037,112714825621,215644478604,412568097507,789319699503,1510115764260

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

%C Thanks to Michael Somos for telling me about Mathematica's SatisfiabilityCount command.

%C Thanks to Doron Zeilberger for telling me about the Noonan-Zeilberger GJs command.

%H Vincenzo Librandi, <a href="/A188765/b188765.txt">Table of n, a(n) for n = 0..1000</a>

%H 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 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 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,1,2,2,1)

%F 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 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 # First download the Maple package DAVID_IAN from the Zeilberger web site

%p read(DAVID_IAN);

%p GJs({0,1},{[0,0,0,0,0],[0,0,1,0,0]},x);

%t a[ n_] := If[ n<0, 0, Length @ Cases[ Tuples[ {0, 1}, n], Except @ {___, 0, 0, _, 0, 0, ___}]] (* _Michael Somos_, Apr 10 2011 *)

%t SPAN = 5; MMM = 60;

%t For[ M=SPAN, M <= MMM, M++,

%t vlist = Array[x, M];

%t cl[i_] := Or[ x[i], x[i+1], x[i+3], x[i+4] ];

%t cl2 = True; For [ i=1, i <= M-SPAN+1, i++, cl2 = And[cl2, cl[i]] ];

%t R[M] = SatisfiabilityCount[ cl2, vlist ] ]

%t Table[ R[M], {M,SPAN,MMM}] (* _N. J. A. Sloane_ *)

%t 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 (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 Cf. A164387.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_, Apr 09 2011