|
Search: id:A082157
|
|
|
| A082157 |
|
Number of deterministic completely defined acyclic automata with 2 inputs and n transient labeled states (and a unique absorbing state). |
|
+0
6
|
|
| 1, 1, 7, 142, 5941, 428856, 47885899, 7685040448, 1681740027657, 482368131521920, 175856855224091311, 79512800815739448576, 43701970591391787395197, 28714779850695689959247872
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
This is the first column of the array A082169.
|
|
REFERENCES
|
V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
|
|
LINKS
|
V. A. Liskovets, Exact enumeration of acyclic deterministic automata,Discrete Appl. Math., 154, No.3 (2006), 537-551.
|
|
FORMULA
|
a(n)=a_2(n) where a_2(0) := 1, a_2(n) := sum(binomial(n, i)*(-1)^(n-i-1)*(i+1)^(2*n-2*i)*a_2(i), i=0..n-1), n>0.
1 = Sum_{n>=0} a(n)*exp(-(1+n)^2*x)*x^n/n!. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jul 18 2005
|
|
EXAMPLE
|
a(2)=7 since the following transition diagrams represent all seven
acyclic automata with two input letters x and y, two transient
states 1 and 2 and the absorbing state 0:
1==x,y==>0==x,y==>0<==x,y==2, 1==x,y==>2==x,y==>0==x,y==>0,
the same with 1 and 2 interchanged,
1--x-->2==x,y==>0==x,y==>0
1--y-->0
and the last one with x and y and/or 1 and 2 interchanged.
|
|
CROSSREFS
|
Sequence in context: A054606 A070074 A051397 this_sequence A104240 A156978 A163028
Adjacent sequences: A082154 A082155 A082156 this_sequence A082158 A082159 A082160
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Valery Liskovets (liskov(AT)im.bas-net.by), Apr 09 2003
|
|
|
Search completed in 0.002 seconds
|
