OFFSET
1,1
COMMENTS
Used in the NRZ encoding to avoid substrings of more than 4 zeros.
REFERENCES
Raphael Reischuk, On avoiding monochrome substrings of length 5.
LINKS
Raphael Reischuk, On avoiding monochrome substrings of length 5.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1).
FORMULA
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
EXAMPLE
a(3) = 2^3 - 1 = 7, since '000' is not a valid string, but all others are.
MATHEMATICA
m[x_] := If[x <= 4, 2^x,
If[x == 5, 31,
m[x - 1] + m[x - 2] + m[x - 3] + m[x - 4] + m[x - 5]]]
c[x_] := If[x <= 2, 0,
If[x == 3, 1,
If[x == 4, 3,
If[x == 5, 6,
If[x == 6, 12,
If[x == 7, 23,
If[x == 8, 45, 2*c[x - 1] - c[x - 6]]]]]]]]
valid[x_] := m[x] - c[x]
CROSSREFS
KEYWORD
nonn
AUTHOR
Raphael Reischuk (raphael(AT)stud.uni-saarland.de), Jun 18 2007
STATUS
approved