login
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
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 Jean-François Alcover), Table of n, a(n) for n = 1..210
Manosij Ghosh Dastidar and Michael Wallner, Asymptotics of relaxed k-ary trees, arXiv:2404.08415 [math.CO], 2024. See p. 1.4.
Valery A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
Valery A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No.3 (2006), 537-551.
FORMULA
a(n) = c_3(n)/(n-1)! where c_3(n) = T_3(n, 1) - sum(binomial(n-1, j-1)*T_3(n-j, j+1)*c_3(j), j=1..n-1) and T_3(0, k) = 1, T_3(n, k) = sum(binomial(n, i)*(-1)^(n-i-1)*(i+k)^(3*n-3*i)*T_3(i, k), i=0..n-1), 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, n-1], Sum[T[n-1, j]*(j+1)*((k+1)*(k+2)/2-j*(j+1)/2), {j, 0, k}]]]]; a[n_] := T[n, n]; Table[a[n], {n, 1, 11} ] (* Jean-François Alcover, Dec 15 2014 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Apr 09 2003
EXTENSIONS
More terms from Paul D. Hanna, Jan 07 2005
STATUS
approved