A322053 Number of decimal strings of length n that contain a specific string xx (where x is a single digit).

0, 1, 19, 280, 3691, 45739, 544870, 6315481, 71743159, 802527760, 8868438271, 97038694279, 1053164192950, 11351825985061, 121644911602099, 1296970638284440, 13767539948978851, 145580595285369619, 1534133217109136230, 16117424311550552641, 168864017757937199839

Offset

1,3

Comments

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

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (19,-81,-90).

Formula

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

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

E.g.f.: exp(10*x) - exp(9*x/2)*(39*cosh(3*sqrt(13)*x/2) + 11*sqrt(13)*sinh(3*sqrt(13)*x/2))/39. - Stefano Spezia, Jun 02 2026

Example

Suppose the desired string is 00. At length 2 that is the only possibility. At length 3 there are 19 strings that contain it: 000, 00d, and d00, where d is any nonzero digit.

Mathematica

Rest[CoefficientList[Series[x^2/((1-10*x)*(1-9*x-9*x^2)), {x, 0, 25}], x]] (* Vincenzo Librandi, Mar 16 2026 *)

Prog

(Magma) R<x>:=PowerSeriesRing(Rationals(), 25); [0] cat Coefficients(R! x^2/((1-10*x)*(1-9*x-9*x^2))); // Vincenzo Librandi, Mar 16 2026
(Python)
n, a0, a1, a2 = 2, 1, 0, 0
print(str(a1)+", "+str(a0), end = ", ")
while n < 21:
    n, a0, a1, a2 = n+1, 19*a0-81*a1-90*a2, a0, a1
    print(a0, end = ", ") # A.H.M. Smeets, May 28 2026
(PARI) concat([0], Vec(x^2/((1-10*x)*(1-9*x-9*x^2)) + O(x^22))) \\ A.H.M. Smeets, May 29 2026

Crossrefs

Cf. A322052, A004189, A322054.

Suggested by A322628.

Sequence in context: A016184 A197742 A322628 * A328916 A081045 A155017

Adjacent sequences: A322050 A322051 A322052 * A322054 A322055 A322056

Keyword

nonn,base,easy

Author

N. J. A. Sloane, Dec 21 2018

Status

approved