OFFSET
0,5
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (20,-100,0,-9,99,-90).
FORMULA
a(0) = a(1) = a(2) = 0, a(3) = 1, a(n) = 9*(10^(n-4) - a(n-4) + sum_{i=3..n-1} a(i)) for n>=4.
G.f.: x^3*(x-1)^2/((10*x-1)*(9*x^5-9*x^4+10*x-1)). - Alois P. Heinz, Feb 26 2015
EXAMPLE
a(3) = 1 because there is only 1 three-digit string that contains the substring "000", i.e., "000" itself.
a(4) = 18 because there are 18 four-digit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" to represent a nonzero digit, the 18 strings comprise 9 of the form "000+" and 9 of the form "+000". ("0000" is excluded.)
a(5) = 261 because there are 261 five-digit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" as above and "." to denote any digit (0 or otherwise), the 261 strings comprise 9*10=90 of the form "000+.", 9*9=81 of the form "+000+", and 10*9=90 of the form ".+000".
a(6) = 3420 because there are 3420 six-digit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" and "." as above, the 3420 strings comprise 9*10*10=900 of the form "000+..", 9*9*10=810 of the form "+000+.", 10*9*9=810 of the form ".+000+", and 10*10*9=900 of the form "..+000".
a(7) = 42291 because there are 42291 seven-digit strings that contain at least one "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" and "." as above, the 42291 strings comprise 9*10*10*10=9000 of the form "000+...", 9*9*10*10=8100 of the form "+000+..", 10*9*9*10=8100 of the form ".+000+.", 10*10*9*9=8100 of the form "..+000+", and 999*9=8991 that are of the form "...+000" but not of the form "000+000" (since 9 strings of that latter form were already counted among the 9000 of the form "000+...").
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Jon E. Schoenfield, Feb 22 2015
STATUS
approved