A125513 a(n) is the number of binary strings of length n such that no subsequence of length 5 or less contains 4 or more ones.

2, 4, 8, 15, 26, 48, 89, 165, 305, 561, 1034, 1908, 3521, 6496, 11982, 22101, 40770, 75210, 138741, 255934, 472117, 870911, 1606567, 2963628, 5466988, 10084919, 18603592, 34317946, 63306130, 116780470, 215424285, 397391986, 733066807

Offset

1,1

Links

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

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

Formula

a(n) = a(n-1) + a(n-2) + a(n-4) + 2*a(n-5) - a(n-7) - a(n-10).

G.f.: x*(2+2*x+2*x^2+3*x^3+x^4-x^5-x^6-x^7-x^8-x^9)/(1-x-x^2-x^4-2*x^5+x^7+x^10). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 26 2009; corrected by R. J. Mathar, Sep 16 2009

Crossrefs

This sequence is similar to the sequences A118647 (where no substring of length 4 contains 3 or more ones), because the number of ones we are checking for is one less than the length of a substring. It is also similar to A120118 (where no substring of length 5 contains 3 or more ones.).

Sequence in context: A182844 A382400 A191630 * A054174 A239890 A331554

Adjacent sequences: A125510 A125511 A125512 * A125514 A125515 A125516

Keyword

nonn,easy

Author

Tanya Khovanova, Dec 28 2006

Status

approved