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
1, 1, 7, 142, 5941, 428856, 47885899, 7685040448, 1681740027657, 482368131521920, 175856855224091311, 79512800815739448576, 43701970591391787395197, 28714779850695689959247872 (list; graph; refs; listen; history; text; internal format)
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: A051397 A322064 A179569 * A258176 A286398 A104240

Adjacent sequences:  A082154 A082155 A082156 * A082158 A082159 A082160

KEYWORD

easy,nonn

AUTHOR

Valery A. Liskovets, Apr 09 2003

STATUS

approved

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 January 24 16:47 EST 2020. Contains 331209 sequences. (Running on oeis4.)