cp's OEIS Frontend

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

%I A082157 #31 Jun 10 2018 04:22:55
%S A082157 1,1,7,142,5941,428856,47885899,7685040448,1681740027657,
%T A082157 482368131521920,175856855224091311,79512800815739448576,
%U A082157 43701970591391787395197,28714779850695689959247872
%N A082157 Number of deterministic completely defined acyclic automata with 2 inputs and n transient labeled states (and a unique absorbing state).
%C A082157 This is the first column of the array A082169.
%H A082157 Vaclav Kotesovec, <a href="/A082157/b082157.txt">Table of n, a(n) for n = 0..220</a>
%H A082157 V. A. Liskovets, <a href="http://igm.univ-mlv.fr/~fpsac/FPSAC03/ARTICLES/5.pdf">Exact enumeration of acyclic automata</a>, Proc. 15th Conf. Formal Power Series and Algebr. Combin. (FPSAC'03), 2003.
%H A082157 V. A. Liskovets, <a href="http://dx.doi.org/10.1016/j.dam.2005.06.009">Exact enumeration of acyclic deterministic automata</a>, Discrete Appl. Math., 154, No.3 (2006), 537-551.
%F A082157 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.
%F A082157 1 = Sum_{n>=0} a(n)*exp(-(1+n)^2*x)*x^n/n!. - _Vladeta Jovovic_, Jul 18 2005
%F A082157 From _Paul D. Hanna_, Jun 04 2011: (Start)
%F A082157 1 = Sum_{n>=0} a(n)*x^n/(1 + (n+1)^2*x)^(n+1).
%F A082157 1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + (n+1)^2*x)^(n+m) for m>=1.
%F A082157 log(1+x) = Sum_{n>=1} a(n)*x^n/(1 + (n+1)^2*x)^n/n. (End)
%e A082157 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:
%e A082157 1==x,y==>0==x,y==>0<==x,y==2, 1==x,y==>2==x,y==>0==x,y==>0,
%e A082157 the same with 1 and 2 interchanged,
%e A082157 1--x-->2==x,y==>0==x,y==>0
%e A082157 1--y-->0
%e A082157 and the last one with x and y and/or 1 and 2 interchanged.
%t A082157 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 *)
%o A082157 (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_
%o A082157 (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)))}
%K A082157 easy,nonn
%O A082157 0,3
%A A082157 _Valery A. Liskovets_, Apr 09 2003