1,2

Coefficients T_2(n,k) form the array A082169. These automata have no nontrivial automorphisms (by states).

V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", Jun 2003.

V. A. Liskovets, Exact enumeration of acyclic deterministic automata,Discrete Appl. Math., 154, No.3 (2006), 537-551.

D. Callan, A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata

a(n) := c_2(n)/(n-1)! where c_2(n) := T_2(n, 1)-sum(binomial(n-1, j-1)*T_2(n-j, j+1)*c_2(j), j=1..n-1) and T_2(0, k) := 1, T_2(n, k) := sum(binomial(n, i)*(-1)^(n-i-1)*(i+k)^(2*n-2*i)*T_2(i, k), i=0..n-1), n>0.

Equals column 0 of triangle A102086. Also equals main diagonal of A102316: a(n) = A102086(n, 0) = A102316(n, n). - Paul D. Hanna (pauldhanna(AT)juno.com), Jan 07 2005

G.f.: 1 = Sum_{n>=0} a(n)*x^n*prod_{k=1, n+1} (1-k*x) for n>0 with a(0)=1. a(n) = -Sum_{k=1, [(n+1)/2]} A008276(n-k+1, k)*a(n-k) where A008276 is Stirling numbers of the first kind. Thus G.f.: 1 = (1-x) + 1*x*(1-x)(1-2x) + 3*x^2*(1-x)(1-2x)(1-3x) + ... + a(n)*x^n*(1-x)(1-2x)(1-3x)*..*(1-(n+1)*x) + ... with a(0)=1. - Paul D. Hanna (pauldhanna(AT)juno.com), Jan 14 2005

a(n) is the determinant of the n X n matrix with (i, j) entry = StirlingCycle[i+1, 2i-j]. - David Callan (callan(AT)stat.wisc.edu), Jul 20 2005

a(2)=3 since the following transition diagrams represent all three initially connected acyclic automata with two input letters x and y, two transient states 1 (initial) and 2, and the absorbing state 0:

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

1--y-->0

and the last one with x and y interchanged.

(PARI) {a(n)=if(n==0, 1, polcoeff(1-sum(k=0, n-1, a(k)*x^k*prod(j=1, k+1, 1-j*x+x*O(x^n))), n))} (Hanna)

(PARI) {a(n)=local(A); if(n<1, 0, A=x+x*O(x^n); for(k=0, n, A+=polcoeff(A, k)*x^k*(1-prod(i=1, k+1, 1-i*x))); polcoeff(A, n))} /* Michael Somos Jan 16 2005 */

Cf. A082157.

Cf. A102086, A102316.

Adjacent sequences: A082158 A082159 A082160 this_sequence A082162 A082163 A082164

Sequence in context: A000951 A000272 A088358 this_sequence A135752 A120021 A131490

easy,nonn

Valery Liskovets (liskov(AT)im.bas-net.by), Apr 09 2003