|
Search: id:A059412
|
|
|
| A059412 |
|
Number of distinct minimal unary DFA's with exactly n states. |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
1,1
|
|
|
REFERENCES
|
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
Jeffrey Shallit, Notes on Enumeration of Finite Automata, manuscript, Jan. 30, 2001
|
|
FORMULA
|
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).
|
|
EXAMPLE
|
a(1) = 2 because there are exactly two minimal unary automata with 1 state.
|
|
CROSSREFS
|
Sequence in context: A130135 A048618 A083554 this_sequence A079472 A006948 A141312
Adjacent sequences: A059409 A059410 A059411 this_sequence A059413 A059414 A059415
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Jeffrey Shallit (shallit(AT)graceland.uwaterloo.ca), Jan 30 2001
|
|
|
Search completed in 0.002 seconds
|
