|
|
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.
|
|
11
|
|
|
0, 1, 18, 252, 3177, 37764, 432315, 4821867, 52767711, 569171142, 6070198824, 64154357361, 673034324472, 7017585817887, 72795938474871, 751858421307975, 7736579039166894, 79354228046171004, 811679794900979769, 8282239107946760700, 84331460977774328115
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
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,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|