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

10, 99, 981, 9720, 96309, 954261, 9455130, 93684519, 928256841, 9197472240, 91131561729, 902961305721, 8946835807050, 88648174014939, 878355088397901, 8703029361715560, 86232460051021149, 854419404714630381, 8465866782890863770

Offset

1,1

Comments

See A322053 for the number that do contain the specified string.

Links

Robert P. P. McKone, Table of n, a(n) for n = 1..1000

Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2024.

Index entries for linear recurrences with constant coefficients, signature (9,9).

Formula

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

a(n) = 9*a(n-1) + 9*a(n-2) for n >= 3.

Example

Suppose the string is 00. At length 2 there are 99 strings that do not contain it. At length 3 there are 19 strings that do not contain it, 000, 00x, and x00, where x is any nonzero digit. So a(3) = 1000-19 = 981.

Mathematica

T[n_, k_] := LinearRecurrence[{n - 1, n - 1}, {n, n^2 - 1}, k];
T[10, {1, 19}] (* Robert P. P. McKone, Dec 31 2020 *)

Crossrefs

Cf. A322052, A004189, A322053.

Suggested by A322628.

Sequence in context: A081109 A242633 A004189 * A179558 A179556 A179477

Adjacent sequences: A322051 A322052 A322053 * A322055 A322056 A322057

Keyword

nonn,base,easy

Author

N. J. A. Sloane, Dec 21 2018

Status

approved