login
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

%I #100 Jul 22 2024 16:04:12

%S 1,2,4,9,8,40,161,14,112,673,20,220,1761,26,364,3641,32,544,6529,38,

%T 760,10641,44,1012,16193,50,1300,23401,56,1624,32481,62,1984,43649,68,

%U 2380,57121,74,2812,73113,80,3280,91841,86,3784,113521,92,4324,138369,98

%N 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.

%C In regular languages, the empty string is considered and since it meets the conditions, a(0)=1.

%D Rodrigo de Castro, Teoría de la computación, 2004, unilibros.

%H Paolo Xausa, <a href="/A340169/b340169.txt">Table of n, a(n) for n = 0..10000</a>

%H Diego Ramírez, <a href="/A340169/a340169_6.pdf">Census Function for a Regular Language</a>

%H <a href="/index/Rec#order_12">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,4,0,0,-6,0,0,4,0,0,-1).

%F a(n) = 4*a(n-3) - 6*a(n-6) + 4*a(n-9) - a(n-12).

%F If n == 0 (mod 3), a(n) = 1 + (8/3)*n - 4*n^2 + (4/3)*n^3.

%F If n == 1 (mod 3), a(n) = 2*n.

%F If n == 2 (mod 3), a(n) = -2*n + 2*n^2.

%F 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

%e a(3)=9, because the strings are aaa, bbb, bbc, bcb, cbb, bcc, cbc, ccb, ccc.

%e a(4)=8, because the strings are aaab, aaba, abaa, baaa, aaac, aaca, acaa, caaa.

%t A340169[n_] := Switch[Mod[n, 3], 0, 4*n*(n-2)*(n-1)/3 + 1, 1, 2*n, 2, 2*n*(n-1)];

%t Array[A340169, 100, 0] (* _Paolo Xausa_, Jul 22 2024 *)

%o (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

%Y Cf. A016933.

%K nonn,easy

%O 0,2

%A _Diego Ramírez_, Feb 25 2021