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

0, 0, 0, 1, 6, 16, 39, 91, 207, 463, 1014, 2188, 4671, 9888, 20786, 43435, 90302, 186934, 385547, 792642, 1625035, 3323393, 6782041, 13813588, 28087444, 57023945, 115614136, 234117510, 473564782, 956961354, 1932059363, 3897575310, 7856867785, 15827584881

Offset

0,5

Links

Matthew House, Table of n, a(n) for n = 0..3304

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

Formula

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

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

a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) + a(n-4) - 4*a(n-6) - a(n-7) + 2*a(n-8) - a(n-10) + 2*a(n-11). - Wesley Ivan Hurt, Feb 12 2026

Mathematica

LinearRecurrence[{3, -1, -2, 1, 0, -4, -1, 2, 0, -1, 2}, {0, 0, 0, 1, 6, 16, 39, 91, 207, 463, 1014}, 40] (* Harvey P. Dale, Jul 19 2020 *)
CoefficientList[Series[x^3*(-1 - 3*x + x^2 + x^3 - x^4 + x^5 + x^6)/((2*x - 1)*(x^10 + x^7 - 2*x^5 - x^4 - x^2 - x + 1)), {x, 0, 40}], x] (* Wesley Ivan Hurt, Feb 12 2026 *)

Crossrefs

Cf. A118647, A118646, A125513.

Sequence in context: A049712 A092274 A068941 * A300371 A009955 A160255

Adjacent sequences: A130899 A130900 A130901 * A130903 A130904 A130905

Keyword

nonn,easy,changed

Author

Tanya Khovanova, Sep 28 2007

Extensions

More terms from Matthew House, Dec 26 2016

Status

approved