A383343 a(n) = 3^n - 3*binomial(n,3) - 3*binomial(n,2) - 2*n - 1.

0, 0, 1, 8, 42, 172, 611, 2004, 6292, 19304, 58533, 176464, 530558, 1593204, 4781575, 14347196, 43044648, 129137680, 387417545, 1162258008, 3486780370, 10460348540, 31381054251, 94143172708, 282429529532, 847288601592, 2541865819501, 7625597475104, 22876792443942, 68630377352644, 205891132081103

Offset: 0

Author

Enrique Navarrete, Apr 23 2025

Keywords

• nonn
• easy

Comments

a(n) is the number of ternary strings of length n that contain at least two 1s or at least three 2s (or both).

Examples

			a(3) = 8 since the strings are 110 (3 of this type), 112 (3 of this type), 111, and 222.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (7,-18,22,-13,3).

Crossrefs

Cf. A127873.

Programs

Mathematica

a[n_] := 3^n - 3*Binomial[n, 3] - 3*Binomial[n, 2] - 2*n - 1; Array[a, 31, 0] (* Amiram Eldar, Apr 24 2025 *)

Formula

a(n) = 7*a(n-1) - 18*a(n-2) + 22*a(n-3) - 13*a(n-4) + 3*a(n-5), n>4.

From Stefano Spezia, Apr 24 2025: (Start)

G.f.: x^2*(1 + x + 4*x^2)/((1 - x)^4*(1 - 3*x)).

E.g.f.: exp(3*x) - exp(x)*(2 + 4*x + 3*x^2 + x^3)/2. (End)

a(n) = 3^n - A127873(n-1).