The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A059412 Number of distinct minimal unary DFA's with exactly n states. 4
 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 (list; graph; refs; listen; history; text; internal format)
 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 REFERENCES M. Domaratzki, D. Kisman, 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 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. FORMULA a(n) = psi(n)+sum(psi(n-j)*2^(j-1), j=1..n-1), where psi(n) is 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 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: A130135 A048618 A083554 * A079472 A308556 A148186 Adjacent sequences:  A059409 A059410 A059411 * A059413 A059414 A059415 KEYWORD nonn AUTHOR Jeffrey Shallit, Jan 30 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 22 15:05 EST 2020. Contains 332137 sequences. (Running on oeis4.)