A255373 Number of strings of n decimal digits that contain at least one string of exactly 3 consecutive "0" digits.

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

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

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

Adjacent sequences: A255370 A255371 A255372 * A255374 A255375 A255376

Keyword

nonn,base,easy

Author

Jon E. Schoenfield, Feb 22 2015

Status

approved