cp's OEIS Frontend

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

%I A118647 #24 May 06 2023 11:13:23
%S A118647 2,4,7,11,19,33,57,97,166,285,489,838,1436,2462,4221,7236,12404,21264,
%T A118647 36453,62491,107127,183646,314822,539695,925191,1586041,2718927,
%U A118647 4661017,7990313,13697676,23481725,40254377,69007488,118298524,202797424
%N A118647 a(n) is the number of binary strings of length n such that no subsequence of length 4 contains 3 or more ones.
%C A118647 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.
%C A118647 For n>=4, a(n) = the sum of all terms in the n-4th power of the 11 X 11 matrix:
%C A118647   [1 1 0 0 0 0 0 0 0 0 0]
%C A118647   [0 0 1 1 0 0 0 0 0 0 0]
%C A118647   [0 0 0 0 1 1 0 0 0 0 0]
%C A118647   [0 0 0 0 0 0 1 0 0 0 0]
%C A118647   [0 0 0 0 0 0 0 1 1 0 0]
%C A118647   [0 0 0 0 0 0 0 0 0 1 0]
%C A118647   [0 0 0 0 0 0 0 0 0 0 1]
%C A118647   [1 1 0 0 0 0 0 0 0 0 0]
%C A118647   [0 0 1 1 0 0 0 0 0 0 0]
%C A118647   [0 0 0 0 1 1 0 0 0 0 0]
%C A118647   [0 0 0 0 0 0 0 1 1 0 0]
%C A118647 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
%C A118647 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.
%D A118647 G. Minkler and J. Minkler, CFAR: The Principles of Automatic Radar Detection in Clutter, Magellan, Baltimore, 1990.
%H A118647 Harvey P. Dale, <a href="/A118647/b118647.txt">Table of n, a(n) for n = 1..1000</a>
%H A118647 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,1,0,-1).
%F A118647 a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-6). - suggested by _Jon E. Schoenfield_
%F A118647 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
%t A118647 LinearRecurrence[{1,1,0,1,0,-1},{2,4,7,11,19,33},40] (* _Harvey P. Dale_, Oct 03 2016 *)
%o A118647 (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
%o A118647 (Magma) R<x>:=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
%o A118647 (SageMath)
%o A118647 def A118647_list(prec):
%o A118647     P.<x> = PowerSeriesRing(ZZ, prec)
%o A118647     return P( x*(2+2*x+x^2-x^4-x^5)/(1-x-x^2-x^4+x^6) ).list()
%o A118647 a=A118647_list(41); a[1:] # _G. C. Greubel_, May 05 2023
%Y A118647 Complementary to A118646: a(n) = 2^n - A118646(n).
%K A118647 nonn,easy
%O A118647 1,1
%A A118647 _Tanya Khovanova_, May 10 2006, Aug 17 2006
%E A118647 More terms from _Joshua Zucker_, Aug 04 2006