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, 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

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.

Links

Diego Ramírez, Table of n, a(n) for n = 0..40

Diego Ramírez, Census Function for a Regular Language

Index entries for linear recurrences with constant coefficients, signature (0,0,4,0,0,-6,0,0,4,0,0,-1).

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.

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

Adjacent sequences: A340166 A340167 A340168 * A340170 A340171 A340172

Keyword

nonn,easy

Author

Diego Ramírez, Feb 25 2021

Status

approved