OFFSET
0,2
COMMENTS
Thanks to Michael Somos for telling me about Mathematica's SatisfiabilityCount command.
Thanks to Doron Zeilberger for telling me about the Noonan-Zeilberger GJs command.
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)
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).
EXAMPLE
1 + 2*x + 4*x^2 + 8*x^3 + 16*x^4 + 30*x^5 + 57*x^6 + 108*x^7 + 207*x^8 + ...
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 *)
PROG
(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 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Apr 09 2011
STATUS
approved