login
A340169
a(n) is the number of strings of length n over the alphabet {a,b,c} with the number of a's divisible by 3, and the number of b's and c's is at most 3.
1
1, 2, 4, 9, 8, 40, 161, 14, 112, 673, 20, 220, 1761, 26, 364, 3641, 32, 544, 6529, 38, 760, 10641, 44, 1012, 16193, 50, 1300, 23401, 56, 1624, 32481, 62, 1984, 43649, 68, 2380, 57121, 74, 2812, 73113, 80, 3280, 91841, 86, 3784, 113521, 92, 4324, 138369, 98
OFFSET
0,2
COMMENTS
In regular languages, the empty string is considered and since it meets the conditions, a(0)=1.
REFERENCES
Rodrigo de Castro, Teoría de la computación, 2004, unilibros.
FORMULA
a(n) = 4*a(n-3) - 6*a(n-6) + 4*a(n-9) - a(n-12).
If n == 0 (mod 3), a(n) = 1 + (8/3)*n - 4*n^2 + (4/3)*n^3.
If n == 1 (mod 3), a(n) = 2*n.
If n == 2 (mod 3), a(n) = -2*n + 2*n^2.
G.f.: (1 + 2*x + 4*x^2 + 5*x^3 + 24*x^5 + 131*x^6 - 6*x^7 - 24*x^8 + 79*x^9 + 4*x^10 - 4x^11)/(1 - x^3)^4. - Stefano Spezia, Feb 28 2021
EXAMPLE
a(3)=9, because the strings are aaa, bbb, bbc, bcb, cbb, bcc, cbc, ccb, ccc.
a(4)=8, because the strings are aaab, aaba, abaa, baaa, aaac, aaca, acaa, caaa.
MATHEMATICA
A340169[n_] := Switch[Mod[n, 3], 0, 4*n*(n-2)*(n-1)/3 + 1, 1, 2*n, 2, 2*n*(n-1)];
Array[A340169, 100, 0] (* Paolo Xausa, Jul 22 2024 *)
PROG
(MATLAB) L=[""]; for k=1:15 L=[L+"a", L+"b", L+"c"]; c=0; for n=1:length(L) if (mod(count(L(n), "a"), 3)==0&& count(L(n), "b")+count(L(l), "c")<=3) c=c+1; end end disp(c) end %show the sequence from 1 to n
CROSSREFS
Cf. A016933.
Sequence in context: A256017 A125752 A103147 * A079781 A163299 A337911
KEYWORD
nonn,easy
AUTHOR
Diego Ramírez, Feb 25 2021
STATUS
approved