|
| |
|
|
A059412
|
|
Number of distinct minimal unary DFA's with exactly n states.
|
|
1
| |
|
|
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; internal format)
|
|
|
|
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 * A079472 A006948 A148186
Adjacent sequences: A059409 A059410 A059411 * A059413 A059414 A059415
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jeffrey Shallit (shallit(AT)graceland.uwaterloo.ca), Jan 30 2001
|
| |
|
|
