login
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

%I #26 Aug 28 2024 11:00:37

%S 0,1,18,252,3177,37764,432315,4821867,52767711,569171142,6070198824,

%T 64154357361,673034324472,7017585817887,72795938474871,

%U 751858421307975,7736579039166894,79354228046171004,811679794900979769,8282239107946760700,84331460977774328115

%N 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.

%C 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.

%H Colin Barker, <a href="/A255371/b255371.txt">Table of n, a(n) for n = 0..999</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (20,-109,99,-90).

%F 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.

%F G.f.: x*(x-1)^2/((10*x-1)*(9*x^3-9*x^2+10*x-1)). - _Alois P. Heinz_, Feb 26 2015

%F 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

%F a(n) ~ 10^n. - _Stefano Spezia_, Aug 28 2024

%e a(1) = 1 because there is only 1 one-digit string that contains a "0" digit, i.e., "0" itself.

%e 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.)

%e 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".

%t LinearRecurrence[{20, -109, 99, -90}, {0, 1, 18, 252}, 30] (* _Paolo Xausa_, Aug 27 2024 *)

%o (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

%Y Cf. A255372-A255380 (for cases k=2 through k=10; see Comments).

%K nonn,base,easy

%O 0,3

%A _Jon E. Schoenfield_, Feb 21 2015

%E a(0)=0 prepended by _Jon E. Schoenfield_, Feb 21 2015