A322052 Number of decimal strings of length n that contain a specific string xy where x and y are distinct digits.

0, 1, 20, 299, 3970, 49401, 590040, 6850999, 77919950, 872348501, 9645565060, 105583302099, 1146187455930, 12356291257201, 132416725116080, 1411810959903599, 14985692873919910, 158445117779295501, 1669465484919035100, 17536209731411055499, 183692631829191519890, 1919390108560504143401

Offset

1,3

Comments

See A004189 for the number that do not contain the specified string.

Links

Robert Israel, Table of n, a(n) for n = 1..999

Index entries for linear recurrences with constant coefficients, signature (20,-101,10).

Formula

G.f.: x^2/((1-10*x)*(1-10*x+x^2)).

a(n) = 10^n - A004189(n+1). - R. J. Mathar, May 28 2026

Example

Suppose the desired string is 03. At length 2 that is the only possibility. At length 3 there are 20 strings that contain it: 03d and d03, where d is any digit.

Maple

f:= gfun:-rectoproc({10*a(n) - 101*a(n + 1) + 20*a(n + 2) - a(n + 3), a(0) = 0, a(1) = 0, a(2) = 1}, a(n), remember):
map(f, [$1..40]); # Robert Israel, Mar 27 2020

Prog

(PARI) a(n)=([0, 1, 0; 0, 0, 1; 10, -101, 20]^(n-1)*[0; 1; 20])[1, 1] \\ Charles R Greathouse IV, May 26 2026

Crossrefs

Cf. A004189, A322053, A322054.

Partial sums of A322628.

Sequence in context: A069326 A001708 A016255 * A250014 A291256 A250015

Adjacent sequences: A322049 A322050 A322051 * A322053 A322054 A322055

Keyword

nonn,base,easy

Author

N. J. A. Sloane, Dec 21 2018

Status

approved