A334656 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, 0, 4, 9, 24, 90, 225, 756, 2160, 6561, 19764, 58806, 177633, 530712, 1595052, 4782969, 14346720, 43053282, 129127041, 387440172, 1162241784, 3486784401, 10460412252, 31380882462, 94143533121, 282429005040, 847289140884, 2541865828329, 7625595890664

Offset

0,3

References

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

Links

Table of n, a(n) for n=0..28.

Brallan S. Rueda Mantilla, Automata, regular expression and recurrence law for a(n)

Index entries for linear recurrences with constant coefficients, signature (0,6,9).

Formula

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

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

G.f.: (1 - 2*x^2)/((1 - 3*x)*(1 + 3*x + 3*x^2)). - Andrew Howroyd, Sep 11 2020

E.g.f.: (exp(3*x) + 2*exp(-3*x/2)*cos(sqrt(3)*x/2))/3. - Stefano Spezia, Sep 11 2020

Example

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).

Mathematica

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 *)
LinearRecurrence[{0, 6, 9}, {1, 0, 4}, 30] (* Harvey P. Dale, Aug 10 2023 *)

Prog

(PARI) Vec((1 - 2*x^2)/((1 - 3*x)*(1 + 3*x + 3*x^2)) + O(x^30)) \\ Andrew Howroyd, Sep 11 2020

Crossrefs

Cf. A000244 (3^n).

Sequence in context: A059507 A128416 A353978 * A175121 A133905 A131826

Adjacent sequences: A334653 A334654 A334655 * A334657 A334658 A334659

Keyword

nonn,easy

Author

Brallan S. Rueda Mantilla, Sep 10 2020

Status

approved