login
A255373
Number of strings of n decimal digits that contain at least one string of exactly 3 consecutive "0" digits.
4
0, 0, 0, 1, 18, 261, 3420, 42291, 503757, 5845383, 66525399, 745904151, 8264888316, 90700808526, 987461965116, 10678505242392, 114817381566435, 1228431892382460, 13086248073415290, 138875261344657416, 1468815363559657773, 15488131104999233505
OFFSET
0,5
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
Cf. A255371, A255372 (for the k=1 and k=2 cases of "exactly k consecutive '0' digits"), A255374-A255380 (for the cases k=4 through k=10).
Sequence in context: A362808 A365137 A255372 * A255374 A255375 A255376
KEYWORD
nonn,base,easy
AUTHOR
Jon E. Schoenfield, Feb 22 2015
STATUS
approved