|
%I #42 Mar 24 2024 18:42:57
%S 2,4,12,30,78,180,432,978,2220,4926,10908,23790,51750,111564,239604,
%T 511758,1089306,2309118,4880946,10285146,21619770,45334776,94865904,
%U 198116082,413013684,859573638,1786263822,3706729488,7681910826
%N Number of distinct minimal unary DFA's with exactly n states.
%C 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 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 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 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 Jeffrey Shallit, Notes on Enumeration of Finite Automata, manuscript, Jan 30, 2001.
%H 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 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 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 a(n) = A027375(n) + A059413(n-1). - _R. J. Mathar_, May 21 2018
%e a(1) = 2 because there are exactly two minimal unary automata with 1 state.
%p A059412 := proc(n)
%p A027375(n)+add(A027375(n-j)*2^(j-1),j=1..n-1) ;
%p end proc:
%p seq(A059412(n),n=1..10) ; # _R. J. Mathar_, May 21 2018
%t A027375[n_] := DivisorSum[n, MoebiusMu[n/#]*2^# &];
%t a[n_] := A027375[n] + Sum[A027375[n-j]*2^(j-1), {j, 1, n-1}];
%t Table[a[n], {n, 1, 29}] (* _Jean-François Alcover_, May 08 2023 *)
%o (PARI) mypsi(n) = sumdiv(n, d, moebius(n/d)*2^d) /* from A027375 */
%o a(n) = mypsi(n) + sum(j=1, n-1, mypsi(n-j)*2^(j-1)) \\ _Michel Marcus_, May 25 2013
%K nonn
%O 1,1
%A _Jeffrey Shallit_, Jan 30 2001
|
