A131283 a(n) is the number of binary strings of length n such that there exist 3 or more ones in a subsequence of length 5 or less.

0, 0, 1, 5, 16, 38, 85, 185, 396, 838, 1748, 3609, 7400, 15097, 30681, 62154, 125588, 253246, 509850, 1025153, 2059159, 4132679, 8288643, 16615051, 33291367, 66682128, 133525499, 267312553, 535049374, 1070786975, 2142690382

Offset

1,4

Links

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

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

Formula

a(n) = 2^n - A120118(n).

a(n)= +3*a(n-1) -2*a(n-2) +a(n-3) -2*a(n-4) +2*a(n-5) -4*a(n-6) -a(n-8) +2*a(n-9) -a(n-10) +2*a(n-11).

G.f.: x^3*(1 +2*x +3*x^2 -x^6 -x^7 -x^3 -2*x^5) / ( (1-2*x)*(1-x-x^3-2*x^5+x^8+x^10) ). - R. J. Mathar, Nov 28 2011

Prog

(PARI) concat([0, 0], Vec(x^3*(1+2*x+3*x^2-x^6-x^7-x^3-2*x^5) / ( (1-2*x)*(1-x-x^3-2*x^5+x^8+x^10) ) + O(x^40))) \\ Michel Marcus, May 28 2020

Crossrefs

Cf. A118646, A118647.

Sequence in context: A174723 A011932 A357289 * A082199 A082190 A155965

Adjacent sequences: A131280 A131281 A131282 * A131284 A131285 A131286

Keyword

nonn,easy

Author

Tanya Khovanova, Sep 28 2007

Status

approved