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

2, 4, 7, 11, 19, 33, 57, 97, 166, 285, 489, 838, 1436, 2462, 4221, 7236, 12404, 21264, 36453, 62491, 107127, 183646, 314822, 539695, 925191, 1586041, 2718927, 4661017, 7990313, 13697676, 23481725, 40254377, 69007488, 118298524, 202797424

Offset: 1

Author

Tanya Khovanova, May 10 2006, Aug 17 2006

Keywords

• nonn
• easy

Comments

Also, 3 ones in a row are not allowed - this additional condition is only relevant for a(3) which has no subsequences of length 4.

For n>=4, a(n) = the sum of all terms in the n-4th power of the 11 X 11 matrix:

[1 1 0 0 0 0 0 0 0 0 0]

[0 0 1 1 0 0 0 0 0 0 0]

[0 0 0 0 1 1 0 0 0 0 0]

[0 0 0 0 0 0 1 0 0 0 0]

[0 0 0 0 0 0 0 1 1 0 0]

[0 0 0 0 0 0 0 0 0 1 0]

[0 0 0 0 0 0 0 0 0 0 1]

[1 1 0 0 0 0 0 0 0 0 0]

[0 0 1 1 0 0 0 0 0 0 0]

[0 0 0 0 1 1 0 0 0 0 0]

[0 0 0 0 0 0 0 1 1 0 0]

because this matrix represents the transitions from the state where the last four bits are 0000, 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1100 to the state after the next bit, always avoiding three 1's out of the last four bits. - Joshua Zucker, Aug 04 2006

Motivated by radar research. In the standard model to get a track on a target you have to get at least M detections out of N observations. See page 96 of Minkler and Minkler. I represented detections as ones and non-detections as zeros. Hence this sequence represents non-tracked situations with n observations.

References

• G. Minkler and J. Minkler, CFAR: The Principles of Automatic Radar Detection in Clutter, Magellan, Baltimore, 1990.

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (1,1,0,1,0,-1).

Crossrefs

Complementary to A118646: a(n) = 2^n - A118646(n).

Programs

Magma

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

Mathematica

LinearRecurrence[{1,1,0,1,0,-1},{2,4,7,11,19,33},40] (* Harvey P. Dale, Oct 03 2016 *)

PARI

Vec(x*(2+2*x+x^2-x^4-x^5)/(1-x-x^2-x^4+x^6) + O(x^100)) \\ Colin Barker, Oct 01 2014

SageMath

def A118647_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(2+2*x+x^2-x^4-x^5)/(1-x-x^2-x^4+x^6) ).list()
a=A118647_list(41); a[1:] # G. C. Greubel, May 05 2023

Formula

a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-6). - suggested by Jon E. Schoenfield

G.f.: x*(2+2*x+x^2-x^4-x^5) / (1-x-x^2-x^4+x^6). - Colin Barker, Oct 01 2014

Extensions

More terms from Joshua Zucker, Aug 04 2006