A188765 Number of binary strings of length n with no substrings equal to 00000 or 00100.
1, 2, 4, 8, 16, 30, 57, 108, 207, 397, 761, 1456, 2784, 5324, 10185, 19488, 37288, 71341, 136486, 261117, 499561, 955756, 1828549, 3498364, 6693021, 12804983, 24498304, 46869822, 89670729, 171556853, 328220258, 627946528, 1201378750, 2298461537, 4397385531, 8413018547, 16095673253, 30794024151, 58914710037, 112714825621, 215644478604, 412568097507, 789319699503, 1510115764260
Offset: 0
Examples
1 + 2*x + 4*x^2 + 8*x^3 + 16*x^4 + 30*x^5 + 57*x^6 + 108*x^7 + 207*x^8 + ...
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- J. Noonan and D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications and implementations
- Doron Zeilberger, Webpage of the paper `The Goulden-Jacskon Cluster Method: Extensions, Applications and Implementations', by John Noonan and Doron Zeilberger
- Index entries for linear recurrences with constant coefficients, signature (1,1,0,1,2,2,1)
Crossrefs
Cf. A164387.
Programs
-
Maple
# First download the Maple package DAVID_IAN from the Zeilberger web site read(DAVID_IAN); GJs({0,1},{[0,0,0,0,0],[0,0,1,0,0]},x); -
Mathematica
a[ n_] := If[ n<0, 0, Length @ Cases[ Tuples[ {0, 1}, n], Except @ {_, 0, 0, , 0, 0, __}]] (* Michael Somos, Apr 10 2011 *) SPAN = 5; MMM = 60; For[ M=SPAN, M <= MMM, M++, vlist = Array[x, M]; cl[i_] := Or[ x[i], x[i+1], x[i+3], x[i+4] ]; cl2 = True; For [ i=1, i <= M-SPAN+1, i++, cl2 = And[cl2, cl[i]] ]; R[M] = SatisfiabilityCount[ cl2, vlist ] ] Table[ R[M], {M,SPAN,MMM}] (* N. J. A. Sloane *) 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 *) -
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 */
Formula
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).
Comments