

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

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^(n2)  a(n2) + sum_{i=1..n1} a(i)) for n>=2.
G.f.: x*(x1)^2/((10*x1)*(9*x^39*x^2+10*x1)).  Alois P. Heinz, Feb 26 2015
a(n) = 20*a(n1)  109*a(n2) + 99*a(n3)  90*a(n4) for n>3.  Colin Barker, Feb 27 2015


EXAMPLE

a(1) = 1 because there is only 1 onedigit string that contains a "0" digit, i.e., "0" itself.
a(2) = 18 because there are 18 twodigit 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 threedigit 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".


PROG

(PARI) concat(0, Vec(x*(x1)^2/((10*x1)*(9*x^39*x^2+10*x1)) + O(x^100))) \\ Colin Barker, Feb 27 2015


CROSSREFS

Cf. A255372A255380 (for cases k=2 through k=10; see Comments).
Sequence in context: A020528 A088924 A125475 * A016175 A062141 A157708
Adjacent sequences: A255368 A255369 A255370 * A255372 A255373 A255374


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



