A365137 a(n) is the number of n-digit numbers that contain '22' in their decimal representation.

0, 0, 1, 18, 261, 3411, 42048, 499131, 5770611, 65427678, 730784601, 8065910511, 88170256008, 956125498671, 10298661792111, 110293085617038, 1175325726682341, 12470569310694411, 131813055336390768, 1388552621823766611, 14583291094441416411, 152746593446386647198

Offset: 0

Author

Felix Huber, Aug 23 2023

Keywords

• nonn
• base
• easy

Comments

a(n) is also valid for '11', '33', '44', '55', '66', '77', '88' or '99' instead of '22'.

Examples

			a(2) = 1, the number 22 itself.
a(3) = 18, 10 numbers 22X plus 9 numbers X22 minus 1 number 222.
a(4) = 261, 100 numbers 22XX plus 90 numbers X22X plus 90 numbers XX22 minus 10 numbers 222X minus 9 numbers X222.
		

Links

• Felix Huber, Table of n, a(n) for n = 0..996
• Armin Widmer, The number of Licence Plates that contain '22'
• Index entries for linear recurrences with constant coefficients, signature (19,-81,-90).

Crossrefs

Cf. A057092, A255372.

Programs

Maple

A365137 := proc(n) option remember; if n <= 1 then 0; elif n = 2 then 1; elif n = 3 then 18; else 19*procname(n - 1) - 81*procname(n - 2) - 90*procname(n - 3); end if; end proc; seq(A365137(n), n = 0 .. 21);

Mathematica

LinearRecurrence[{19, -81, -90}, {0, 0, 1, 18}, 22] (* Robert P. P. McKone, Aug 24 2023 *)

Formula

a(n) = 19*a(n - 1) - 81*a(n - 2) - 90*a(n - 3) with a(0) = a(1) = 0, a(2) = 1 and a(3) = 18 for n >= 4.

a(n) = 9*10^(n - 1) - A057092(n) + A057092(n - 2) with a(0) = a(1) = 0 for n >= 2.

a(0) = 0, a(n) = 9*10^(n - 1) - (p^(n + 1) - q^(n + 1))/(3*sqrt(13)) + (p^(n - 1) - q^(n - 1))/(3*sqrt(13)) with p = (9 + 3*sqrt(13))/2 and q = (9 - 3*sqrt(13))/2 for n >= 1.

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

a(n) = A255372(n) for n <= 5.