cp's OEIS Frontend

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

%I A059412 #45 Nov 05 2024 10:48:23
%S A059412 2,4,12,30,78,180,432,978,2220,4926,10908,23790,51750,111564,239604,
%T A059412 511758,1089306,2309118,4880946,10285146,21619770,45334776,94865904,
%U A059412 198116082,413013684,859573638,1786263822,3706729488,7681910826
%N A059412 Number of distinct minimal unary DFA's with exactly n states.
%C A059412 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
%C A059412 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
%C A059412 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
%D A059412 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).
%D A059412 Jeffrey Shallit, Notes on Enumeration of Finite Automata, manuscript, Jan 30, 2001.
%H A059412 Cyril Nicaud, <a href="https://hal-upec-upem.archives-ouvertes.fr/hal-00620109">Average state complexity of operations on unary automata</a>, Math. Foundations of Computer Science, 1999, Lect. Notes in Computer Sci. #1672, pp. 231-240.
%H A059412 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).
%H A059412 Lucas Vieira Barbosa, <a href="https://doi.org/10.25365/thesis.76733">Nonclassical Temporal Correlations Under Finite-Memory Constraints</a>, Doctoral Thesis, Univ. Wien (Austria 2024). See p. 35.
%F A059412 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).
%F A059412 a(n) = A027375(n) + A059413(n-1). - _R. J. Mathar_, May 21 2018
%e A059412 a(1) = 2 because there are exactly two minimal unary automata with 1 state.
%p A059412 A059412 := proc(n)
%p A059412     A027375(n)+add(A027375(n-j)*2^(j-1),j=1..n-1) ;
%p A059412 end proc:
%p A059412 seq(A059412(n),n=1..10) ; # _R. J. Mathar_, May 21 2018
%t A059412 A027375[n_] := DivisorSum[n, MoebiusMu[n/#]*2^# &];
%t A059412 a[n_] := A027375[n] + Sum[A027375[n-j]*2^(j-1), {j, 1, n-1}];
%t A059412 Table[a[n], {n, 1, 29}] (* _Jean-François Alcover_, May 08 2023 *)
%o A059412 (PARI) mypsi(n) = sumdiv(n, d, moebius(n/d)*2^d) /* from A027375 */
%o A059412 a(n) = mypsi(n) + sum(j=1, n-1, mypsi(n-j)*2^(j-1)) \\ _Michel Marcus_, May 25 2013
%K A059412 nonn
%O A059412 1,1
%A A059412 _Jeffrey Shallit_, Jan 30 2001