%I #29 Nov 22 2019 12:35:45
%S 0,0,0,1,3,8,18,39,81,164,326,639,1239,2382,4548,8635,16319,30722,
%T 57650,107885,201425,375322,698162,1296801,2405707,4457984,8253228,
%U 15266969,28220967,52134000,96257558,177640983,327696621,604287700,1113981922,2053015399
%N Number of length n binary words that contain 111 but do not contain 000 (as contiguous subwords).
%C For n>=1, a(n) = A000073(n+3) - 2*A000045(n+1).
%H Colin Barker, <a href="/A238361/b238361.txt">Table of n, a(n) for n = 0..1000</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-1,-2,-1).
%F G.f.: (x^3*(1 + x + x^2))/((1 - x - x^2)*(1 - x - x^2 - x^3)).
%F 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
%e There are a(6) = 18 such binary words:
%e 01: 001110
%e 02: 001111
%e 03: 010111
%e 04: 011100
%e 05: 011101
%e 06: 011110
%e 07: 011111
%e 08: 100111
%e 09: 101110
%e 10: 101111
%e 11: 110111
%e 12: 111001
%e 13: 111010
%e 14: 111011
%e 15: 111100
%e 16: 111101
%e 17: 111110
%e 18: 111111
%t nn=30;CoefficientList[Series[(x^3+x^4+x^5)/(1-2x-x^2+x^3+2x^4+x^5),{x,0,nn}],x]
%o (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
%K nonn,easy
%O 0,5
%A _Geoffrey Critzer_, Mar 08 2014