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

1, 7, 139, 5711, 408354, 45605881, 7390305396, 1647470410551, 485292763088275, 183049273155939442, 86211400693272461866

Offset: 1

Author

Valery A. Liskovets, Apr 09 2003

Keywords

• easy
• nonn

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.

Crossrefs

Cf. A082158, A082161.

Cf. A102098, A102400.

Programs

Mathematica

T[n_, k_] := T[n, k] = If[nJean-François Alcover, Dec 15 2014 *)

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

Extensions

More terms from Paul D. Hanna, Jan 07 2005