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
Links
- Index entries for linear recurrences with constant coefficients, signature (3,-2,1,-2,2,-4,0,-1,2,-1,2).
Programs
-
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
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