A391468 Number of words of length 3n formed with 3 types of letter where the number of each type == 0 (mod 3).

1, 3, 63, 2187, 59535, 1594323, 43033599, 1162261467, 31381413903, 847288609443, 22876782889023, 617673396283947, 16677181957946895, 450283905890997363, 12157665452083359999, 328256967394537077627, 8862938119840787453583, 239299329230617529590083

Offset

0,2

Comments

Among all 3*n words, the number of letters of each type can be taken in 4 cases: all of the form 3*k, all 3*k+1, all 3*k+2, or one each 3*k, 3*k+1, 3*k+2; for total a(n) + A391469(n) + A391470(n) + 2*A013733(n-1) = 3^(3*n).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..700 (first 101 terms from Pablo Serra)

Pablo Serra, On the number of words of N = 3*M letters with a three-letter alphabet, arXiv:2512.22362 [math.CO], 2025.

Index entries for linear recurrences with constant coefficients, signature (27,-27,729).

Formula

a(n) = Sum_{n1+n2+n3=n} trinomial(3*n; 3*n1, 3*n2, 3*n3).

a(n) = 3^(3*n-2) + (1 + (-1)^n)*i^n*3^((3*n-2)/2) for n>=1, where i is the imaginary unit.

a(n) = 27*(a(n-1) - a(n-2) + 27*a(n-3)), for n >= 4.

G.f.: (162*x^3-9*x^2+24*x-1)/((27*x-1)*(27*x^2+1)).

E.g.f.: (2 + exp(27*x) + 6*cos(3*sqrt(3)*x))/9. - Stefano Spezia, Dec 30 2025

Example

For n=1, the a(1) = 3 words are AAA, BBB, and CCC.
For n=2, there are 3 single letter words XXXXXX, and binomial(6,3)=20 ways to inter-mingle XXX and YYY followed by 3 choices of the omitted type so a(2) = 3 + 3*20 = 63.

Mathematica

LinearRecurrence[{27, -27, 729}, {1, 3, 63, 2187}, 20] (* Paolo Xausa, Jan 16 2026 *)

Crossrefs

Cf. A391469, A391470, A013733.

Cf. A007613, A054879.

Sequence in context: A331012 A384018 A386416 * A369955 A123687 A159605

Adjacent sequences: A391465 A391466 A391467 * A391469 A391470 A391471

Keyword

nonn,easy

Author

Pablo Serra, Dec 29 2025

Status

approved