A164387 Number of binary strings of length n with no substrings equal to 0000 or 0010.

1, 2, 4, 8, 14, 25, 45, 82, 149, 270, 489, 886, 1606, 2911, 5276, 9562, 17330, 31409, 56926, 103173, 186991, 338903, 614229, 1113231, 2017624, 3656749, 6627505, 12011714, 21770074, 39456161, 71510489, 129605869, 234898146, 425730250, 771595046, 1398441654

Offset: 0

Author

R. H. Hardin, Aug 14 2009

Keywords

• nonn
• easy

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

Examples

			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
		

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).

Crossrefs

Cf. A209400.

Programs

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 *)

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

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)

Extensions

Edited by N. J. A. Sloane, Mar 31 2011