%I #13 Jun 13 2015 00:51:38
%S 2,4,7,13,25,49,97,191,375,737,1449,2849,5601,11011,21647,42557,83665,
%T 164481,323361,635711,1249775,2456993,4830321,9496161,18668961,
%U 36702211,72154647,141852301,278874281,548252401,1077835841,2118969471
%N Number of n-bit strings that contain no more than 4 zeros and no more than 2 leading and 2 trailing zeros.
%C Used in the NRZ encoding to avoid substrings of more than 4 zeros.
%D Raphael Reischuk, On avoiding monochrome substrings of length 5.
%H Raphael Reischuk, <a href="http://www.raphaelreischuk.de/pub/nubfals.pdf">On avoiding monochrome substrings of length 5</a>.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1,1).
%F G.f.: 2*x+4*x^2 -x^3*(7+6*x+5*x^2+4*x^3+3*x^4) / ( -1+x+x^2+x^3+x^4+x^5 ). - _R. J. Mathar_, Oct 27 2012
%e a(3) = 2^3 - 1 = 7, since '000' is not a valid string, but all others are.
%t m[x_] := If[x <= 4, 2^x,
%t If[x == 5, 31,
%t m[x - 1] + m[x - 2] + m[x - 3] + m[x - 4] + m[x - 5]]]
%t c[x_] := If[x <= 2, 0,
%t If[x == 3, 1,
%t If[x == 4, 3,
%t If[x == 5, 6,
%t If[x == 6, 12,
%t If[x == 7, 23,
%t If[x == 8, 45, 2*c[x - 1] - c[x - 6]]]]]]]]
%t valid[x_] := m[x] - c[x]
%K nonn
%O 1,1
%A Raphael Reischuk (raphael(AT)stud.uni-saarland.de), Jun 18 2007
|