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
Examples
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.
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.
Programs
-
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 *) -
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)))}
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)
Comments