|
Search: id:A059413
|
|
|
| A059413 |
|
Number of distinct languages accepted by unary DFA's with n states. |
|
+0
1
|
|
| 2, 6, 18, 48, 126, 306, 738, 1716, 3936, 8862, 19770, 43560, 95310, 206874, 446478, 958236, 2047542, 4356660, 9237606, 19522752, 41142522, 86477298, 181343202, 379459284, 792472968, 1652046606, 3438310428, 7145039916, 14826950742
(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
|
sum(psi(t)*2^(n-t), t=1..n), 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 languages accepted by unary DFA's with 1 state.
|
|
CROSSREFS
|
Sequence in context: A072827 A002529 A018027 this_sequence A062026 A048495 A089380
Adjacent sequences: A059410 A059411 A059412 this_sequence A059414 A059415 A059416
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Jeffrey Shallit (shallit(AT)graceland.uwaterloo.ca), Jan 30 2001
|
|
|
Search completed in 0.002 seconds
|
