A384198 a(n) = 3^(n-3)*(binomial(n,3) + 3*binomial(n,2) + 9*n + 27).

1, 4, 16, 64, 255, 1008, 3942, 15228, 58077, 218700, 813564, 2991816, 10884699, 39208536, 139946130, 495303012, 1739406393, 6064804692, 21006799848, 72318491280, 247561692471, 843026984064, 2856838685886, 9637472084364, 32374793163285, 108327417770268, 361133233980372

Offset: 0

Author

Enrique Navarrete, May 21 2025

Keywords

• nonn
• easy

Comments

a(n) is the number of words of length n defined on 4 letters where a chosen letter (for example, the first letter of the alphabet) is used at most three times.

Examples

			a(5) = 1008 since from the 1024 words defined on {0, 1, 2, 3} we subtract the 5 permutations of 00001, the 5 permutations of 00002, the 5 permutations of 00003, and 00000.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (12,-54,108,-81).

Crossrefs

Cf. A382618.

Programs

Mathematica

LinearRecurrence[{12, -54, 108, -81}, {1, 4, 16, 64}, 30] (* or *)
A384198[n_] := 3^(n - 3)*(Binomial[n, 3] + 3*Binomial[n, 2] + 9*n + 27);
Array[A384198, 30, 0] (* Paolo Xausa, Jun 30 2025 *)

Formula

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

G.f.: (1 - 8*x + 22*x^2 - 20*x^3)/(1 - 3*x)^4. - Stefano Spezia, May 22 2025