A255371 Number of strings of n decimal digits that contain at least one "0" digit that is not part of a string of two or more consecutive "0" digits.
0, 1, 18, 252, 3177, 37764, 432315, 4821867, 52767711, 569171142, 6070198824, 64154357361, 673034324472, 7017585817887, 72795938474871, 751858421307975, 7736579039166894, 79354228046171004, 811679794900979769, 8282239107946760700, 84331460977774328115
Offset: 0
Examples
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".
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).
Programs
-
Mathematica
LinearRecurrence[{20, -109, 99, -90}, {0, 1, 18, 252}, 30] (* Paolo Xausa, Aug 27 2024 *) -
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
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
Extensions
a(0)=0 prepended by Jon E. Schoenfield, Feb 21 2015
Comments