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,2

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).

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

Example

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.

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 *)

Prog

(Magma) R<x>:=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
(SageMath)
def A120118_list(prec):
    P.<x> = 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

Crossrefs

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

Sequence in context: A357308 A357933 A237821 * A108895 A146929 A146921

Adjacent sequences: A120115 A120116 A120117 * A120119 A120120 A120121

Keyword

nonn,easy

Author

Tanya Khovanova, Aug 15 2006, Oct 11 2006

Status

approved