login
a(n) is the number of words of length n on the alphabet {0,1,2} with the number of 0's plus the number of 1's congruent to the number of 2's modulo 3.
1

%I #49 Aug 10 2023 13:50:39

%S 1,0,4,9,24,90,225,756,2160,6561,19764,58806,177633,530712,1595052,

%T 4782969,14346720,43053282,129127041,387440172,1162241784,3486784401,

%U 10460412252,31380882462,94143533121,282429005040,847289140884,2541865828329,7625595890664

%N a(n) is the number of words of length n on the alphabet {0,1,2} with the number of 0's plus the number of 1's congruent to the number of 2's modulo 3.

%D Thomas A. Sudkamp, An Introduction to Languages and Machines. second edition 1997 Addison-Wesley.

%H Brallan S. Rueda Mantilla, <a href="/A334656/a334656_1.pdf">Automata, regular expression and recurrence law for a(n)</a>

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

%F a(n) = 3^(n-1) + (1/3)*(-3/2 + sqrt(3)*i/2)^n + (1/3)*(-3/2 - sqrt(3)*i/2)^n.

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

%F G.f.: (1 - 2*x^2)/((1 - 3*x)*(1 + 3*x + 3*x^2)). - _Andrew Howroyd_, Sep 11 2020

%F E.g.f.: (exp(3*x) + 2*exp(-3*x/2)*cos(sqrt(3)*x/2))/3. - _Stefano Spezia_, Sep 11 2020

%e The a(3)=9 words are (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1), (2,2,2).

%t CoefficientList[Series[(1 - 2 x^2)/((1 - 3 x) (1 + 3 x + 3 x^2)), {x, 0, 28}], x] (* _Michael De Vlieger_, Sep 11 2020 *)

%t LinearRecurrence[{0,6,9},{1,0,4},30] (* _Harvey P. Dale_, Aug 10 2023 *)

%o (PARI) Vec((1 - 2*x^2)/((1 - 3*x)*(1 + 3*x + 3*x^2)) + O(x^30)) \\ _Andrew Howroyd_, Sep 11 2020

%Y Cf. A000244 (3^n).

%K nonn,easy

%O 0,3

%A _Brallan S. Rueda Mantilla_, Sep 10 2020