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
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Apr 09 2003
STATUS
approved