cp's OEIS Frontend

A118646 a(n) is the number of binary strings of length n such that there exists a subsequence of length 4 containing 3 or more ones.

%I A118646 #19 May 06 2023 09:02:05
%S A118646 0,0,1,5,13,31,71,159,346,739,1559,3258,6756,13922,28547,58300,118668,
%T A118646 240880,487835,986085,1990025,4010658,8073786,16237521,32629241,
%U A118646 65522823,131498801,263774439,528880599,1060044148,2124001923
%N A118646 a(n) is the number of binary strings of length n such that there exists a subsequence of length 4 containing 3 or more ones.
%C A118646 Or there are 3 ones in a row - this is relevant only for a(3).
%C A118646 Complementary to A118647, namely a(n) = 2^(n+3) - A118647(n).
%H A118646 G. C. Greubel, <a href="/A118646/b118646.txt">Table of n, a(n) for n = 1..1000</a>
%H A118646 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-2,1,-2,-1,2).
%F A118646 a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-6) + 13*2^(n-6).
%F A118646 a(n) = +3*a(n-1) -a(n-2) -2*a(n-3) +a(n-4) -2*a(n-5) -a(n-6) +2*a(n-7).
%F A118646 G.f.: x^3*(1+2*x-x^2-x^3)/( (1-2*x)*(1-x-x^2-x^4+x^6) ). - _R. J. Mathar_, Nov 28 2011
%e A118646 a(4) is 5 because only the following binary strings of length 4 satisfy the conditions: 0111, 1011, 1101, 1011, 1111.
%t A118646 LinearRecurrence[{3,-1,-2,1,-2,-1,2}, {0,0,1,5,13,31,71}, 41] (* _G. C. Greubel_, May 05 2023 *)
%o A118646 (Magma) R<x>:=PowerSeriesRing(Integers(), 40); [0,0] cat Coefficients( R!( x^3*(1+2*x-x^2-x^3)/((1-2*x)*(1-x-x^2-x^4+x^6)) )); // _G. C. Greubel_, May 05 2023
%o A118646 (SageMath)
%o A118646 def A118646_list(prec):
%o A118646     P.<x> = PowerSeriesRing(ZZ, prec)
%o A118646     return P( x^3*(1+2*x-x^2-x^3)/((1-2*x)*(1-x-x^2-x^4+x^6)) ).list()
%o A118646 a=A118646_list(41); a[1:] # _G. C. Greubel_, May 05 2023
%Y A118646 Cf. A118647.
%K A118646 nonn
%O A118646 1,4
%A A118646 _Tanya Khovanova_, May 10 2006, Aug 17 2006