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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A120118 a(n) is the number of binary strings of length n such that no subsequence of length 5 or less contains 3 or more ones. 3
2, 4, 7, 11, 16, 26, 43, 71, 116, 186, 300, 487, 792, 1287, 2087, 3382, 5484, 8898, 14438, 23423, 37993, 61625, 99965, 162165, 263065, 426736, 692229, 1122903, 1821538, 2954849, 4793266, 7775472, 12613097, 20460538, 33190414, 53840404 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

LINKS

Table of n, a(n) for n=1..36.

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

FORMULA

a(n) = a(n-1) + a(n-3) + 2a(n-5) - a(n-8) - a(n-10).

G.f. -x*(1+x+x^2)*(x^7+x^5+x^4-x^3-x^2-2) / ( 1-x-x^3-2*x^5+x^8+x^10 ). - R. J. Mathar, Nov 28 2011

EXAMPLE

This sequence is similar to A118647 - where no subsequence of length 4 contains 3 ones. It is obvious that the first 4 terms of these two sequences are the same. There are only 3 sequences of length 5 that contain 3 ones such that no subsequence of length 4 contains 3 ones: 10101, 11001, 10011. Hence the fifth term for this sequence is 3 less than the corresponding term of A118647.

MATHEMATICA

LinearRecurrence[{1, 0, 1, 0, 2, 0, 0, -1, 0, -1}, {2, 4, 7, 11, 16, 26, 43, 71, 116, 186}, 50] (* Harvey P. Dale, Nov 27 2013 *)

CROSSREFS

Sequence in context: A063676 A099385 A237821 * A108895 A146929 A146921

Adjacent sequences:  A120115 A120116 A120117 * A120119 A120120 A120121

KEYWORD

nonn

AUTHOR

Tanya Khovanova, Aug 15 2006, Oct 11 2006

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 June 28 15:15 EDT 2017. Contains 288838 sequences.