A386293 a(n) = 9^n - (1/2)*4^n, n > 0; a(0) = 0.

0, 7, 73, 697, 6433, 58537, 529393, 4774777, 43013953, 387289417, 3486260113, 31378962457, 282421147873, 2541832273897, 22876658237233, 205890595223737, 1853018041368193, 16677173109731977, 150094600937260753, 1350851580234038617, 12157664909301114913

Offset

0,2

Comments

a(n) is the number of ternary strings of length 2*n that exclude strings with only 0's and 2's with an even number of each.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..300

Index entries for linear recurrences with constant coefficients, signature (13,-36).

Formula

a(n) = 13*a(n-1) - 36*a(n-2), n > 2.

G.f.: (7*x - 18*x^2)/((1 - 4*x)*(1 - 9*x)).

E.g.f.: exp(9*x) - (1/2)*exp(4*x) - 1/2.

Example

For n = 2, a(2) = 73 since from the 81 strings of length 4 we exclude the following 8 (number of permutations in parentheses): 0022 (6), 0000 (1), 2222 (1).
For n = 3, a(3) = 697 since from the 729 strings of length 6 we exclude the following 32 (number of permutations in parentheses): 000000 (1), 000022 (15), 002222 (15), 222222 (1).

Mathematica

CoefficientList[Series[(7*x-18*x^2)/((1-4*x)*(1-9*x)), {x, 0, 25}], x] (* Vincenzo Librandi, Jul 23 2025 *)

Prog

(Magma) [0] cat [9^n - (1/2)*4^n: n in [1..30]]; // Vincenzo Librandi, Jul 23 2025

Crossrefs

Cf. A386227.

Sequence in context: A240195 A025592 A009142 * A155614 A113033 A093675

Adjacent sequences: A386290 A386291 A386292 * A386294 A386295 A386296

Keyword

nonn,easy

Author

Enrique Navarrete, Jul 17 2025

Status

approved