A120118 a(n) is the number of binary strings of length n such that no subsequence of length 5 or less contains 3 or more ones.

1, 2, 4, 7, 11, 16, 26, 43, 71, 116, 186, 300, 487, 792, 1287, 2087, 3382, 5484, 8898, 14438, 23423, 37993, 61625, 99965, 162165, 263065, 426736, 692229, 1122903, 1821538, 2954849, 4793266, 7775472, 12613097, 20460538, 33190414, 53840404

Offset: 0

Author

Tanya Khovanova, Aug 15 2006, Oct 11 2006

Keywords

• nonn
• easy

Examples

			This sequence is similar to A118647 - where no subsequence of length 4 contains 3 ones. It is obvious that the first 4 terms of these two sequences are the same. There are only 3 sequences of length 5 that contain 3 ones such that no subsequence of length 4 contains 3 ones: 10101, 11001, 10011. Hence the fifth term for this sequence is 3 less than the corresponding term of A118647.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Kees Immink and Kui Cai, Properties and constructions of energy-harvesting sliding-window constrained codes, IEEE Comm. Lett., May 2020.
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,0,2,0,0,-1,0,-1).

Crossrefs

Cf. A118647, A133523, A133551, A334251, A335247.

Programs

Magma

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( 1 +x*(1 +x+x^2)*(2+x^2+x^3-x^4-x^5-x^7)/(1-x-x^3-2*x^5+x^8+x^10) )); // G. C. Greubel, May 05 2023

Mathematica

LinearRecurrence[{1,0,1,0,2,0,0,-1,0,-1}, {1,2,4,7,11,16,26,43,71,116, 186}, 50] (* Harvey P. Dale, Nov 27 2013 *)

SageMath

def A120118_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1 +x*(1+x+x^2)*(2+x^2+x^3-x^4-x^5-x^7)/(1-x-x^3-2*x^5 +
     x^8+x^10) ).list()
A120118_list(40) # G. C. Greubel, May 05 2023

Formula

a(n) = a(n-1) + a(n-3) + 2*a(n-5) - a(n-8) - a(n-10).

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