|
| |
|
|
A082157
|
|
Number of deterministic completely defined acyclic automata with 2 inputs and n transient labeled states (and a unique absorbing state).
|
|
7
| |
|
|
1, 1, 7, 142, 5941, 428856, 47885899, 7685040448, 1681740027657, 482368131521920, 175856855224091311, 79512800815739448576, 43701970591391787395197, 28714779850695689959247872
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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
Contribution from Paul D. Hanna, Jun 4 2011: (Start)
1 = Sum_{n>=0} a(n)*x^n/(1 + (n+1)^2*x)^(n+1).
1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + (n+1)^2*x)^(n+m) for m>=1.
log(1+x) = Sum_{n>=1} a(n)*x^n/(1 + (n+1)^2*x)^n/n. (End)
|
|
|
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.
|
|
|
PROG
| (PARI) {a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+(k+1)^2*x+x*O(x^n))^(k+1)), n)} /* From Paul D. Hanna */
(PARI) {a(n)=if(n==0, 1, sum(k=0, n-1, -(-1)^(n-k)*binomial(n, k)*(k+1)^(2*(n-k))*a(k)))}
|
|
|
CROSSREFS
| Sequence in context: A070074 A051397 A179569 * A104240 A156978 A163028
Adjacent sequences: A082154 A082155 A082156 * A082158 A082159 A082160
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Valery Liskovets (liskov(AT)im.bas-net.by), Apr 09 2003
|
| |
|
|
