A328916 Number of n-digit decimal numbers containing 123 as a substring.

0, 0, 0, 1, 19, 280, 3699, 45971, 549430, 6390601, 72860039, 818050960, 9074118999, 99668329951, 1085865248550, 11749578366501, 126396115335059, 1352875288102040, 14417003302653899, 153043636911203931, 1619083493823937270, 17076417934936718801, 179611135712455984079

Offset

0,5

Comments

See A322628 for the number of n-digit decimal numbers containing 12 as a substring.

Links

Michael Gutierrez, Table of n, a(n) for n = 0..997

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

Formula

a(n) = 10*a(n-1) + 9*10^(n-4) - a(n-3).

G.f.: x^3*(1 - x)/((1 - 10*x)*(1 - 10*x + x^3)). - Andrew Howroyd, Nov 14 2025

Example

For n=6, there are a(6)=3699 six-digit numbers that contain 123 as a substring.

Mathematica

CoefficientList[Series[x^3*(1 - x)/((1 - 10*x)*(1 - 10*x + x^3)), {x, 0, 21}], x] (* Stefano Spezia, Jun 02 2026 *)

Prog

(Python)
a = [0, 0, 0, 1]
for i in range(0, 18):
    a.append(10 * a[len(a) - 1] + 9 * 10 ** (len(a) - 4) - a[len(a) - 3])
print(a)

Crossrefs

Cf. A322628.

Sequence in context: A197742 A322628 A322053 * A081045 A155017 A386956

Adjacent sequences: A328913 A328914 A328915 * A328917 A328918 A328919

Keyword

nonn,base,easy

Author

Michael Gutierrez, Oct 30 2019

Status

approved