A118871 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

A118871

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

2

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

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

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

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

EXAMPLE

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

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

PROG

(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

(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

CROSSREFS

Cf. A112575, A118430, A118869, A118870.

Sequence in context: A129953 A079859 A298802 * A019494 A192886 A079844

Adjacent sequences: A118868 A118869 A118870 * A118872 A118873 A118874

KEYWORD

nonn

AUTHOR

Emeric Deutsch, May 03 2006

STATUS

approved