A238361 Number of length n binary words that contain 111 but do not contain 000 (as contiguous subwords).

0, 0, 0, 1, 3, 8, 18, 39, 81, 164, 326, 639, 1239, 2382, 4548, 8635, 16319, 30722, 57650, 107885, 201425, 375322, 698162, 1296801, 2405707, 4457984, 8253228, 15266969, 28220967, 52134000, 96257558, 177640983, 327696621, 604287700, 1113981922, 2053015399

Offset

0,5

Comments

For n>=1, a(n) = A000073(n+3) - 2*A000045(n+1).

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (2,1,-1,-2,-1).

Formula

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

a(n) = 2*a(n-1) + a(n-2) - a(n-3) - 2*a(n-4) - a(n-5) for n>5. - Colin Barker, Nov 22 2019

Example

There are a(6) = 18 such binary words:
01:  001110
02:  001111
03:  010111
04:  011100
05:  011101
06:  011110
07:  011111
08:  100111
09:  101110
10:  101111
11:  110111
12:  111001
13:  111010
14:  111011
15:  111100
16:  111101
17:  111110
18:  111111

Mathematica

nn=30; CoefficientList[Series[(x^3+x^4+x^5)/(1-2x-x^2+x^3+2x^4+x^5), {x, 0, nn}], x]

Prog

(PARI) concat([0, 0, 0], Vec(x^3*(1 + x + x^2) / ((1 - x - x^2)*(1 - x - x^2 - x^3)) + O(x^40))) \\ Colin Barker, Nov 22 2019

Crossrefs

Sequence in context: A117727 A117713 A128552 * A178420 A011377 A036385

Adjacent sequences: A238358 A238359 A238360 * A238362 A238363 A238364

Keyword

nonn,easy

Author

Geoffrey Critzer, Mar 08 2014

Status

approved