cp's OEIS Frontend

A118871 Number of binary sequences of length n containing exactly one subsequence 0101.

%I A118871 #13 Sep 08 2022 08:45:25
%S A118871 0,0,0,0,1,4,10,24,57,128,278,596,1260,2628,5430,11136,22683,45936,
%T A118871 92574,185764,371347,739840,1469580,2911224,5753048,11343800,22322444,
%U A118871 43845120,85973013,168314604,329041842,642385248,1252552077,2439430272,4745767138,9223159852
%N A118871 Number of binary sequences of length n containing exactly one subsequence 0101.
%C A118871 With only two 0's at the beginning, the convolution of A112575 with itself. Column 1 of A118869.
%H A118871 G. C. Greubel, <a href="/A118871/b118871.txt">Table of n, a(n) for n = 0..1000</a>
%H A118871 <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,8,-11,8,-6,4,-1).
%F A118871 G.f.: x^4/(1-2*x+x^2-2*x^3+x^4)^2.
%F A118871 a(n) = Sum_{j=0..n-4} A112575(j+1)*A112575(n-j-3). - _G. C. Greubel_, Jan 14 2022
%e A118871 a(5) = 4 because we have 01010, 01011, 00101 and 10101.
%p A118871 g:=z^4/(1-2*z+z^2-2*z^3+z^4)^2: gser:=series(g,z=0,40): seq(coeff(gser, z, n), n=0..35);
%t A118871 LinearRecurrence[{4,-6,8,-11,8,-6,4,-1}, {0,0,0,0,1,4,10,24}, 40] (* _G. C. Greubel_, Jan 14 2022 *)
%o A118871 (Magma) R<x>:=PowerSeriesRing(Integers(), 40); [0,0,0,0] cat Coefficients(R!( x^4/(1 -2*x +x^2 -2*x^3 +x^4)^2 )); // _G. C. Greubel_, Jan 14 2022
%o A118871 (Sage)
%o A118871 @CachedFunction
%o A118871 def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))
%o A118871 def A118871(n): return sum( A112575(j+1)*A112575(n-j-3) for j in (0..n-4) )
%o A118871 [A118871(n) for n in (0..40)] # _G. C. Greubel_, Jan 14 2022
%Y A118871 Cf. A112575, A118430, A118869, A118870.
%K A118871 nonn
%O A118871 0,6
%A A118871 _Emeric Deutsch_, May 03 2006