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

3, 12, 54, 210, 798, 2850, 10038, 34410, 116406, 388362, 1283430, 4203786, 13675038, 44211570, 142202574, 455299242, 1451997726, 4614253122, 14617620726, 46177325994, 145505603694, 457437342546, 1435074324006, 4493508791754, 14045385985902

Offset: 1

Author

Lucas B. Vieira, Mar 02 2024

Keywords

• nonn

Comments

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

Examples

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

References

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

Links

• Lucas B. Vieira and Costantino Budroni, Temporal correlations in the simplest measurement sequences, Quantum 6 p. 623 (2022).

Crossrefs

Cf. A059412 for the case of binary strings.

Cf. A143324 for psi(k,n).

Programs

Mathematica

NumPrimitiveWords[k_, n_] := Sum[MoebiusMu[d] k^(n/d), {d, Divisors[n]}];
a[n_] := NumPrimitiveWords[3, n] + Sum[(3 - 1) 3^(i - 1) NumPrimitiveWords[3, n - i], {i, 1, n - 1}]

Formula

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