OFFSET
0,2
COMMENTS
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
LINKS
N. J. A. Sloane, Table of n, a(n) for n = 0..1000 [Replaces R. H. Hardin's b-file of 500 terms]
Index entries for linear recurrences with constant coefficients, signature (1,1,0,1,1).
FORMULA
From N. J. A. Sloane, Mar 31 2011: (Start)
For n >= 5, a(n) = a(n-1) + a(n-2) + a(n-4) + a(n-5).
G.f.: (1 + x + x^2 + 2*x^3 + x^4)/(1 - x - x^2 - x^4 - x^5). (End)
EXAMPLE
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
MAPLE
f:=proc(n) option remember;
if n <= 3 then 2^n elif n=4 then 14
else f(n-1)+f(n-2)+f(n-4)+f(n-5); fi; end;
MATHEMATICA
LinearRecurrence[{1, 1, 0, 1, 1}, {1, 2, 4, 8, 14}, 40] (* David Nacin, Mar 07 2012 *)
PROG
(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
(Python)
def a(n, adict={0:1, 1:2, 2:4, 3:8, 4:14}):
if n in adict:
return adict[n]
adict[n]=a(n-1)+a(n-2)+a(n-4)+a(n-5)
return adict[n] # David Nacin, Mar 07 2012
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Aug 14 2009
EXTENSIONS
Edited by N. J. A. Sloane, Mar 31 2011
STATUS
approved