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

Author

Tanya Khovanova, Dec 28 2006

Keywords

• nonn

Links

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

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

Formula

a(n) = a(n-1) + a(n-2) + a(n-4) + 2a(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) [From Maksym Voznyy (voznyy(AT)mail.ru), Jul 26 2009]

Extensions

G.f. proposed by Maksym Voznyy checked and corrected by R. J. Mathar, Sep 16 2009.