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

Author

Alois P. Heinz, Aug 04 2008

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A000045, A000930, first column of A143291.

Programs

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

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

Formula

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

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