login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A082157 Number of deterministic completely defined acyclic automata with 2 inputs and n transient labeled states (and a unique absorbing state). 10

%I

%S 1,1,7,142,5941,428856,47885899,7685040448,1681740027657,

%T 482368131521920,175856855224091311,79512800815739448576,

%U 43701970591391787395197,28714779850695689959247872

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

%C This is the first column of the array A082169.

%H Vaclav Kotesovec, <a href="/A082157/b082157.txt">Table of n, a(n) for n = 0..220</a>

%H 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 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 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 1 = Sum_{n>=0} a(n)*exp(-(1+n)^2*x)*x^n/n!. - _Vladeta Jovovic_, Jul 18 2005

%F From _Paul D. Hanna_, Jun 04 2011: (Start)

%F 1 = Sum_{n>=0} a(n)*x^n/(1 + (n+1)^2*x)^(n+1).

%F 1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + (n+1)^2*x)^(n+m) for m>=1.

%F log(1+x) = Sum_{n>=1} a(n)*x^n/(1 + (n+1)^2*x)^n/n. (End)

%e 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 1==x,y==>0==x,y==>0<==x,y==2, 1==x,y==>2==x,y==>0==x,y==>0,

%e the same with 1 and 2 interchanged,

%e 1--x-->2==x,y==>0==x,y==>0

%e 1--y-->0

%e and the last one with x and y and/or 1 and 2 interchanged.

%t 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 (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 (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 easy,nonn

%O 0,3

%A _Valery A. Liskovets_, Apr 09 2003

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 24 22:04 EST 2020. Contains 332216 sequences. (Running on oeis4.)