

A118646


a(n) is the number of binary strings of length n such that there exists a subsequence of length 4 containing 3 or more ones.


3



0, 0, 1, 5, 13, 31, 71, 159, 346, 739, 1559, 3258, 6756, 13922, 28547, 58300, 118668, 240880, 487835, 986085, 1990025, 4010658, 8073786, 16237521, 32629241, 65522823, 131498801, 263774439, 528880599, 1060044148, 2124001923
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Or there are 3 ones in a row  this is relevant only for a(3).
Complementary to A118647, namely a(n) = 2^(n+3)  A118647(n).


LINKS

Table of n, a(n) for n=1..31.
Index entries for linear recurrences with constant coefficients, signature (3,1,2,1,2,1,2).


FORMULA

a(n) = a(n1) + a(n2) + a(n4)  a(n6) + 13*2^(n6).
a(n)= +3*a(n1) a(n2) 2*a(n3) +a(n4) 2*a(n5) a(n6) +2*a(n7).
G.f. x^3*(12*x+x^2+x^3) / ( (2*x1)*(x^6x^4x^2x+1) ).  R. J. Mathar, Nov 28 2011


EXAMPLE

a(4) is 5 because only the following binary strings of length 4 satisfy the conditions: 0111, 1011, 1101, 1011, 1111.


CROSSREFS

Sequence in context: A109419 A067333 A209009 * A097969 A082280 A007708
Adjacent sequences: A118643 A118644 A118645 * A118647 A118648 A118649


KEYWORD

nonn


AUTHOR

Tanya Khovanova, May 10 2006, Aug 17 2006


STATUS

approved



