login
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
OFFSET
0,3
COMMENTS
This is the first column of the array A082169.
LINKS
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
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Apr 09 2003
STATUS
approved