A059412 Number of distinct minimal unary DFA's with exactly n states.

2, 4, 12, 30, 78, 180, 432, 978, 2220, 4926, 10908, 23790, 51750, 111564, 239604, 511758, 1089306, 2309118, 4880946, 10285146, 21619770, 45334776, 94865904, 198116082, 413013684, 859573638, 1786263822, 3706729488, 7681910826

Offset

1,1

Comments

Also, number of binary strings w of length 2n such that the longest suffix of w appearing at least twice in w is of length n. - Jeffrey Shallit, Mar 20 2017

Also, number of ultimately periodic binary sequences uvvvv... with |u|+|v| = n, formula uses psi(|v|) and 2^(|u|-1), plus psi(n) for u empty. - Michael Vielhaber, Mar 19 2022

Also, number of minimal length-n binary patterns, each corresponding to a minimal n-state deterministic Mealy automaton outputting some binary string. Used in the definition of the Deterministic Complexity (DC) of a string w, i.e., DC(w) = n. - Lucas B. Vieira, Mar 02 2024

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

Jeffrey Shallit, Notes on Enumeration of Finite Automata, manuscript, Jan 30, 2001.

Links

Table of n, a(n) for n=1..29.

Cyril Nicaud, Average state complexity of operations on unary automata, Math. Foundations of Computer Science, 1999, Lect. Notes in Computer Sci. #1672, pp. 231-240.

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

Formula

a(n) = psi(n) + Sum_{j=1..n-1} psi(n-j)*2^(j-1), where psi(n) is the number of primitive words of length n over a 2-letter alphabet (expressible in terms of the Moebius function).

a(n) = A027375(n) + A059413(n-1). - R. J. Mathar, May 21 2018

Example

a(1) = 2 because there are exactly two minimal unary automata with 1 state.

Maple

A059412 := proc(n)
    A027375(n)+add(A027375(n-j)*2^(j-1), j=1..n-1) ;
end proc:
seq(A059412(n), n=1..10) ; # R. J. Mathar, May 21 2018

Mathematica

A027375[n_] := DivisorSum[n, MoebiusMu[n/#]*2^# &];
a[n_] := A027375[n] + Sum[A027375[n-j]*2^(j-1), {j, 1, n-1}];
Table[a[n], {n, 1, 29}] (* Jean-François Alcover, May 08 2023 *)

Prog

(PARI) mypsi(n) = sumdiv(n, d, moebius(n/d)*2^d) /* from A027375 */
a(n) = mypsi(n) + sum(j=1, n-1, mypsi(n-j)*2^(j-1)) \\ Michel Marcus, May 25 2013

Crossrefs

Sequence in context: A048618 A083554 A355384 * A079472 A366590 A308556

Adjacent sequences: A059409 A059410 A059411 * A059413 A059414 A059415

Keyword

nonn

Author

Jeffrey Shallit, Jan 30 2001

Status

approved