login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #22 Jul 03 2022 07:56:18

%S 0,0,1,18,261,3411,42057,499383,5775480,65506986,731953926,8082054387,

%T 88382960316,958831580700,10332164902851,110698940875149,

%U 1180155371168034,12527193711780981,132468636134059128,1396061253467955315,14668489189614036627

%N Number of strings of n decimal digits that contain at least one string of exactly 2 consecutive "0" digits.

%H Alois P. Heinz, <a href="/A255372/b255372.txt">Table of n, a(n) for n = 0..1000</a>

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

%F a(0) = a(1) = 0, a(2) = 1, a(n) = 9*(10^(n-3) - a(n-3) + Sum_{i=2..n-1} a(i)) for n>=3.

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

%e a(2) = 1 because there is only 1 two-digit string that contains the substring "00", i.e., "00" itself.

%e a(3) = 18 because there are 18 three-digit strings that contain a "00" substring that is not part of a string of three or more consecutive "0" digits; using "+" to represent a nonzero digit, the 18 strings comprise 9 of the form "00+" and 9 of the form "+00". ("000" is excluded.)

%e a(4) = 261 because there are 261 four-digit strings that contain a "00" substring that is not part of a string of three 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 "00+.", 9*9=81 of the form "+00+", and 10*9=90 of the form ".+00".

%e a(5) = 3411 because there are 3411 five-digit strings that contain at least one "00" substring that is not part of a string of three or more consecutive "0" digits; using "+" and "." as above, the 3411 strings comprise 9*10*10=900 of the form "00+..", 9*9*10=810 of the form "+00+.", 10*9*9=810 of the form ".+00+", and 99*9=891 that are of the form "..+00" but not of the form "00+00" (since the 9 strings of that latter form were already counted among the 900 of the form "00+..").

%t LinearRecurrence[{20,-100,-9,99,-90},{0,0,1,18,261},30] (* _Harvey P. Dale_, Jan 01 2021 *)

%Y Cf. A255371 (for strings with, as it were, "exactly 1 consecutive '0' digit", i.e., a "0" that is not a substring of a longer string of "0" digits) and A255373-A255380 (for strings of exactly k consecutive "0" digits, for the cases k=3 through k=10).

%K nonn,base,easy

%O 0,4

%A _Jon E. Schoenfield_, Feb 21 2015