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

%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