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

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A164428 Number of binary strings of length n with no substrings equal to 0000, 0011, or 1001. 1
1, 2, 4, 8, 13, 22, 37, 62, 104, 175, 294, 494, 830, 1395, 2344, 3939, 6619, 11123, 18691, 31409, 52780, 88693, 149041, 250452, 420864, 707229, 1188441, 1997081, 3355934, 5639380, 9476526, 15924546, 26759925, 44967917, 75564988, 126980925, 213381292 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

R. H. Hardin and Harvey P. Dale, Table of n, a(n) for n = 0..1000 (terms n=4..500 from R. H. Hardin)

Index entries for linear recurrences with constant coefficients, signature (1,1,0,1,-1).

FORMULA

G.f.: -(x+1)*(x^2+1)*(x^4-x^3-1)/(x^5-x^4-x^2-x+1). - R. J. Mathar, Jan 19 2011

EXAMPLE

From Tom Edgar, Feb 10 2015: (Start)

When n=4, there are 16 binary strings of length 4 and 3 of them are the ones to avoid, so a(4) = 13.

When n=5, there are 32 binary strings of length 5; the ones including a substring of the indicated form are '00000', '10000', '00001', '00011', '10011', '00110', '00111', 01001', '11001', and '10010'. Since there are 10 to avoid, we have a(5) = 22.

(End)

MATHEMATICA

Join[{1, 2, 4}, LinearRecurrence[{1, 1, 0, 1, -1}, {8, 13, 22, 37, 62}, 40]] (* Harvey P. Dale, Feb 10 2015 *)

CROSSREFS

Sequence in context: A164413 A164441 A023600 * A164507 A164411 A074467

Adjacent sequences:  A164425 A164426 A164427 * A164429 A164430 A164431

KEYWORD

nonn

AUTHOR

R. H. Hardin, Aug 14 2009

EXTENSIONS

Offset changed, terms prepended accordingly, and b-file amended by Harvey P. Dale, Feb 11 2015

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 16 15:11 EST 2018. Contains 318172 sequences. (Running on oeis4.)