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

 

Logo


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

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.

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.

License Agreements, Terms of Use, Privacy Policy. .

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