cp's OEIS Frontend

A255373 Number of strings of n decimal digits that contain at least one string of exactly 3 consecutive "0" digits.

%I A255373 #18 Aug 25 2016 17:13:36
%S A255373 0,0,0,1,18,261,3420,42291,503757,5845383,66525399,745904151,
%T A255373 8264888316,90700808526,987461965116,10678505242392,114817381566435,
%U A255373 1228431892382460,13086248073415290,138875261344657416,1468815363559657773,15488131104999233505
%N A255373 Number of strings of n decimal digits that contain at least one string of exactly 3 consecutive "0" digits.
%H A255373 Alois P. Heinz, <a href="/A255373/b255373.txt">Table of n, a(n) for n = 0..1000</a>
%H A255373 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (20,-100,0,-9,99,-90).
%F A255373 a(0) = a(1) = a(2) = 0, a(3) = 1, a(n) = 9*(10^(n-4) - a(n-4) + sum_{i=3..n-1} a(i)) for n>=4.
%F A255373 G.f.: x^3*(x-1)^2/((10*x-1)*(9*x^5-9*x^4+10*x-1)). - _Alois P. Heinz_, Feb 26 2015
%e A255373 a(3) = 1 because there is only 1 three-digit string that contains the substring "000", i.e., "000" itself.
%e A255373 a(4) = 18 because there are 18 four-digit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" to represent a nonzero digit, the 18 strings comprise 9 of the form "000+" and 9 of the form "+000". ("0000" is excluded.)
%e A255373 a(5) = 261 because there are 261 five-digit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" as above and "." to denote any digit (0 or otherwise), the 261 strings comprise 9*10=90 of the form "000+.", 9*9=81 of the form "+000+", and 10*9=90 of the form ".+000".
%e A255373 a(6) = 3420 because there are 3420 six-digit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" and "." as above, the 3420 strings comprise 9*10*10=900 of the form "000+..", 9*9*10=810 of the form "+000+.", 10*9*9=810 of the form ".+000+", and 10*10*9=900 of the form "..+000".
%e A255373 a(7) = 42291 because there are 42291 seven-digit strings that contain at least one "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" and "." as above, the 42291 strings comprise 9*10*10*10=9000 of the form "000+...", 9*9*10*10=8100 of the form "+000+..", 10*9*9*10=8100 of the form ".+000+.", 10*10*9*9=8100 of the form "..+000+", and 999*9=8991 that are of the form "...+000" but not of the form "000+000" (since 9 strings of that latter form were already counted among the 9000 of the form "000+...").
%Y A255373 Cf. A255371, A255372 (for the k=1 and k=2 cases of "exactly k consecutive '0' digits"), A255374-A255380 (for the cases k=4 through k=10).
%K A255373 nonn,base,easy
%O A255373 0,5
%A A255373 _Jon E. Schoenfield_, Feb 22 2015