OFFSET
0,3
COMMENTS
Let A(n,k) be the number of strings of n decimal digits that contain at least one string of exactly k consecutive "0" digits (i.e., at least one string of k consecutive "0" digits that is not part of a string of more than k consecutive "0" digits). This sequence gives the values of A(n,k) for k=1.
LINKS
Colin Barker, Table of n, a(n) for n = 0..999
Index entries for linear recurrences with constant coefficients, signature (20,-109,99,-90).
FORMULA
a(0)=0, a(1)=1, a(n) = 9*(10^(n-2) - a(n-2) + sum_{i=1..n-1} a(i)) for n>=2.
G.f.: x*(x-1)^2/((10*x-1)*(9*x^3-9*x^2+10*x-1)). - Alois P. Heinz, Feb 26 2015
a(n) = 20*a(n-1) - 109*a(n-2) + 99*a(n-3) - 90*a(n-4) for n>3. - Colin Barker, Feb 27 2015
a(n) ~ 10^n. - Stefano Spezia, Aug 28 2024
EXAMPLE
a(1) = 1 because there is only 1 one-digit string that contains a "0" digit, i.e., "0" itself.
a(2) = 18 because there are 18 two-digit strings that contain a "0" digit that is not part of a string of two or more consecutive "0" digits; using "+" to represent a nonzero digit, the 18 strings comprise 9 of the form "0+" and 9 of the form "+0". ("00" is excluded.)
a(3) = 252 because there are 252 three-digit strings that contain at least one "0" digit that is not part of a string of two or more consecutive "0" digits; using "+" as above, the 252 strings comprise 81 of the form "0++", 81 of the form "+0+", 81 of the form "++0", and 9 of the form "0+0".
MATHEMATICA
LinearRecurrence[{20, -109, 99, -90}, {0, 1, 18, 252}, 30] (* Paolo Xausa, Aug 27 2024 *)
PROG
(PARI) concat(0, Vec(x*(x-1)^2/((10*x-1)*(9*x^3-9*x^2+10*x-1)) + O(x^100))) \\ Colin Barker, Feb 27 2015
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Jon E. Schoenfield, Feb 21 2015
EXTENSIONS
a(0)=0 prepended by Jon E. Schoenfield, Feb 21 2015
STATUS
approved