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

0, 0, 0, 1, 13, 106, 694, 3991, 21067, 104680, 497452, 2285053, 10222777, 44788342, 192970834, 820244467, 3448381783, 14367483412, 59421385000, 244271688313, 999169721125, 4070288777410, 16525230017710, 66906367267471, 270271938430243

Offset: 0

Author

Enrique Navarrete, May 28 2025

Keywords

• nonn
• easy

Comments

a(n) is the number of strings of length n defined on {0, 1, 2, 3} that contain at least three 0's.

Examples

			a(4) = 13 since the strings are the 4 permutations of 0001, the 4 permutations of 0002, the 4 permutations of 0003 and 0000.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (13,-63,135,-108).

Crossrefs

Cf. A086443, A345954.

Programs

Mathematica

a[n_]:=4^n - 3^n - n*3^(n-1) - Binomial[n,2]*3^(n-2); Array[a,25,0] (* Stefano Spezia, May 29 2025 *)

Formula

E.g.f.: exp(3*x)*(exp(x) - x^2/2 - x - 1).

G.f.: x^3/((1 - 3*x)^3*(1 - 4*x)). - Stefano Spezia, May 29 2025