A082157 Number of deterministic completely defined acyclic automata with 2 inputs and n transient labeled states (and a unique absorbing state).

1, 1, 7, 142, 5941, 428856, 47885899, 7685040448, 1681740027657, 482368131521920, 175856855224091311, 79512800815739448576, 43701970591391787395197, 28714779850695689959247872

Offset

0,3

Comments

This is the first column of the array A082169.

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..220

V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. Formal Power Series and Algebr. Combin. (FPSAC'03), 2003.

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, Jul 18 2005

From Paul D. Hanna, Jun 04 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.

Mathematica

a[0] = 1; a[n_] := a[n] = Sum[-(-1)^(n-k)*Binomial[n, k]*(k+1)^(2*(n-k))*a[k], {k, 0, n-1}]; Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Dec 15 2014, translated from PARI *)

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)} \\ 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: A322064 A179569 A342812 * A258176 A333088 A286398

Adjacent sequences: A082154 A082155 A082156 * A082158 A082159 A082160

Keyword

easy,nonn

Author

Valery A. Liskovets, Apr 09 2003

Status

approved