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.

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

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

G. C. Greubel, Table of n, a(n) for n = 1..1000

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

Formula

a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-6) + 13*2^(n-6).

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

G.f.: x^3*(1+2*x-x^2-x^3)/( (1-2*x)*(1-x-x^2-x^4+x^6) ). - 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.

Mathematica

LinearRecurrence[{3, -1, -2, 1, -2, -1, 2}, {0, 0, 1, 5, 13, 31, 71}, 41] (* G. C. Greubel, May 05 2023 *)

Prog

(Magma) R<x>:=PowerSeriesRing(Integers(), 40); [0, 0] cat Coefficients( R!( x^3*(1+2*x-x^2-x^3)/((1-2*x)*(1-x-x^2-x^4+x^6)) )); // G. C. Greubel, May 05 2023
(SageMath)
def A118646_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P( x^3*(1+2*x-x^2-x^3)/((1-2*x)*(1-x-x^2-x^4+x^6)) ).list()
a=A118646_list(41); a[1:] # G. C. Greubel, May 05 2023

Crossrefs

Cf. A118647.

Sequence in context: A067333 A369176 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