

A082162


Number of deterministic completely defined initially connected acyclic automata with 3 inputs and n transient unlabeled states (and a unique absorbing state).


12



1, 7, 139, 5711, 408354, 45605881, 7390305396, 1647470410551, 485292763088275, 183049273155939442, 86211400693272461866
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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


REFERENCES

R. Bacher, C. Reutenauer, The number of right ideals of given codimension over a finite field, in Noncommutative Birational Geometry, Representations and Combinatorics, edited by Arkady. Berenstein and Vladimir. Retakha, Contemporary Mathematics, Vol. 592, 2013.


LINKS

Vaclav Kotesovec (after JeanFrançois Alcover), Table of n, a(n) for n = 1..210
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), 537551.


FORMULA

a(n) = c_3(n)/(n1)! where c_3(n) = T_3(n, 1)  sum(binomial(n1, j1)*T_3(nj, j+1)*c_3(j), j=1..n1) and T_3(0, k) = 1, T_3(n, k) = sum(binomial(n, i)*(1)^(ni1)*(i+k)^(3*n3*i)*T_3(i, k), i=0..n1), n>0.
Equals column 0 of triangle A102098. Also equals main diagonal of A102400: a(n) = A102098(n, 0) = A102400(n, n).  Paul D. Hanna, Jan 07 2005


MATHEMATICA

T[n_, k_] := T[n, k] = If[n<k  k<0, 0, If[k == 0, 1, If[n == k, T[n, n1], Sum[T[n1, j]*(j+1)*((k+1)*(k+2)/2j*(j+1)/2), {j, 0, k}]]]]; a[n_] := T[n, n]; Table[a[n], {n, 1, 11} ] (* JeanFrançois Alcover, Dec 15 2014 *)


CROSSREFS

Cf. A082158, A082161.
Cf. A102098, A102400.
Sequence in context: A221375 A190195 A126156 * A280629 A238692 A288322
Adjacent sequences: A082159 A082160 A082161 * A082163 A082164 A082165


KEYWORD

easy,nonn


AUTHOR

Valery A. Liskovets, Apr 09 2003


EXTENSIONS

More terms from Paul D. Hanna, Jan 07 2005


STATUS

approved



