

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.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


LINKS

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


FORMULA

a(n) = a(n1) + a(n2) + a(n4) + 2a(n5)  a(n7)  a(n10).
G.f.: x*(2+2*x+2*x^2+3*x^3+x^4x^5x^6x^7x^8x^9)/(1xx^2x^42*x^5+x^7+x^ 10) [From Maksym Voznyy (voznyy(AT)mail.ru), Jul 26 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.).


KEYWORD

nonn


AUTHOR



EXTENSIONS

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


STATUS

approved



