cp's OEIS Frontend

A370821 Number of minimal deterministic Mealy automata with n states outputting ternary strings.

%I A370821 #14 Jul 23 2025 16:05:12
%S A370821 3,12,54,210,798,2850,10038,34410,116406,388362,1283430,4203786,
%T A370821 13675038,44211570,142202574,455299242,1451997726,4614253122,
%U A370821 14617620726,46177325994,145505603694,457437342546,1435074324006,4493508791754,14045385985902
%N A370821 Number of minimal deterministic Mealy automata with n states outputting ternary strings.
%C A370821 a(n) counts the minimal number of ternary words w = uv, with |w| = n, such that u is an irreducible prefix and v a primitive word. This defines a minimal "pattern", written as "u(v)", describing the behavior of a minimal n-state deterministic Mealy automaton outputting a string from a ternary alphabet, where u is the transient output, and v the cyclic output, possibly truncated. Used in the definition of the Deterministic Complexity (DC) of strings (Vieira and Budroni, 2022).
%D A370821 M. Domaratzki, D. Kisman, and J. Shallit, On the number of distinct languages accepted by finite automata with n states, J. Autom. Lang. Combinat. 7 (2002) 4-18, Section 6, f_1(n).
%H A370821 Lucas B. Vieira and Costantino Budroni, <a href="https://doi.org/10.22331/q-2022-01-18-623">Temporal correlations in the simplest measurement sequences</a>, Quantum 6 p. 623 (2022).
%F A370821 a(n) = psi(3, n) + Sum_{i=1..n-1} (3-1)*3^(i-1)*psi(3, n-i), where psi(k,n) is the number of primitive words of length n on a k-letter alphabet (Cf. A143324).
%e A370821 a(1) = 3 as there are only 3 deterministic Mealy automata with 1 state producing ternary words, corresponding to the 3 patterns (0), (1) and (2), generating the strings w=0^L, w=1^L, and w=2^L for L >= 1.
%e A370821 a(2) = 12, since there are 12 minimal ternary patterns: (01), 0(1), (02), 0(2), (10), 1(0), (12), 1(2), (20), 2(0), (21), 2(1).
%e A370821 E.g.: The ternary string w = 000120120 can be described by the pattern 00(012), where the parentheses indicate the repeating part, up to truncation. This pattern is minimal, with 5 symbols (ignoring the parentheses). It describes the behavior of a minimal deterministic Mealy automaton producing the string w, leading to its Deterministic Complexity (DC) to be DC(w) = 5.
%t A370821 NumPrimitiveWords[k_, n_] := Sum[MoebiusMu[d] k^(n/d), {d, Divisors[n]}];
%t A370821 a[n_] := NumPrimitiveWords[3, n] + Sum[(3 - 1) 3^(i - 1) NumPrimitiveWords[3, n - i], {i, 1, n - 1}]
%Y A370821 Cf. A059412 for the case of binary strings.
%Y A370821 Cf. A143324 for psi(k,n).
%K A370821 nonn
%O A370821 1,1
%A A370821 _Lucas B. Vieira_, Mar 02 2024