login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A164387 Number of binary strings of length n with no substrings equal to 0000 or 0010 4
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 (list; graph; refs; listen; history; text; internal format)
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

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). - N. J. A. Sloane, Mar 31 2011

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

Cf.A209400

Sequence in context: A164151 A281810 A199925 * A164150 A164149 A164148

Adjacent sequences:  A164384 A164385 A164386 * A164388 A164389 A164390

KEYWORD

nonn,easy

AUTHOR

R. H. Hardin Aug 14 2009

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 21 04:10 EDT 2017. Contains 290857 sequences.