A143281 Number of binary words of length n containing at least one subword 101 and no subword 11.

0, 0, 0, 1, 2, 4, 8, 15, 27, 48, 84, 145, 248, 421, 710, 1191, 1989, 3309, 5487, 9073, 14966, 24634, 40472, 66384, 108729, 177858, 290610, 474364, 773615, 1260643, 2052818, 3340662, 5433345, 8832432, 14351403, 23309326, 37844645, 61423513, 99663191, 161665653

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

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

a(n) = A000045(n+2)-A000930(n+2).

Example

a(6)=8 because 8 binary words of length 6 have at least one substring 101 and no substring 11: 000101, 001010, 010100, 101000, 010101, 101010, 101001, 100101.

Maple

a:= n-> coeff(series(x^3/((x^2+x-1)*(x^3+x-1)), x, n+1), x, n):
seq(a(n), n=0..60);

Mathematica

CoefficientList[Series[x^3/((x^2+x-1)*(x^3+x-1)), {x, 0, 50}], x] (* G. C. Greubel, Apr 28 2017 *)

Prog

(PARI) x='x+O('x^50); concat([0, 0, 0], Vec(x^3/((x^2+x-1)*(x^3+x-1)))) \\ G. C. Greubel, Apr 28 2017

Crossrefs

Cf. A000045, A000930, first column of A143291.

Sequence in context: A000126 A344611 A182716 * A098057 A289692 A074029

Adjacent sequences: A143278 A143279 A143280 * A143282 A143283 A143284

Keyword

nonn

Author

Alois P. Heinz, Aug 04 2008

Status

approved