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

0, 0, 0, 0, 1, 4, 10, 24, 57, 128, 278, 596, 1260, 2628, 5430, 11136, 22683, 45936, 92574, 185764, 371347, 739840, 1469580, 2911224, 5753048, 11343800, 22322444, 43845120, 85973013, 168314604, 329041842, 642385248, 1252552077, 2439430272, 4745767138, 9223159852

Offset: 0

Author

Emeric Deutsch, May 03 2006

Keywords

• nonn

Comments

With only two 0's at the beginning, the convolution of A112575 with itself. Column 1 of A118869.

Examples

			a(5) = 4 because we have 01010, 01011, 00101 and 10101.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (4,-6,8,-11,8,-6,4,-1).

Crossrefs

Cf. A112575, A118430, A118869, A118870.

Programs

Magma

R:=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

Maple

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

Mathematica

LinearRecurrence[{4,-6,8,-11,8,-6,4,-1}, {0,0,0,0,1,4,10,24}, 40] (* G. C. Greubel, Jan 14 2022 *)

Sage

@CachedFunction
def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))
def A118871(n): return sum( A112575(j+1)*A112575(n-j-3) for j in (0..n-4) )
[A118871(n) for n in (0..40)] # G. C. Greubel, Jan 14 2022

Formula

G.f.: x^4/(1-2*x+x^2-2*x^3+x^4)^2.

a(n) = Sum_{j=0..n-4} A112575(j+1)*A112575(n-j-3). - G. C. Greubel, Jan 14 2022