|
%I #29 Apr 18 2024 12:50:35
%S 1,7,139,5711,408354,45605881,7390305396,1647470410551,
%T 485292763088275,183049273155939442,86211400693272461866
%N Number of deterministic completely defined initially connected acyclic automata with 3 inputs and n transient unlabeled states (and a unique absorbing state).
%C Coefficients T_3(n,k) form the array A082170. These automata have no nontrivial automorphisms (by states).
%D 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.
%H Vaclav Kotesovec (after Jean-François Alcover), <a href="/A082162/b082162.txt">Table of n, a(n) for n = 1..210</a>
%H Manosij Ghosh Dastidar and Michael Wallner, <a href="https://arxiv.org/abs/2404.08415">Asymptotics of relaxed k-ary trees</a>, arXiv:2404.08415 [math.CO], 2024. See p. 1.4.
%H Valery A. Liskovets, <a href="http://igm.univ-mlv.fr/~fpsac/FPSAC03/ARTICLES/5.pdf">Exact enumeration of acyclic automata</a>, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
%H Valery A. Liskovets, <a href="http://dx.doi.org/10.1016/j.dam.2005.06.009">Exact enumeration of acyclic deterministic automata</a>, Discrete Appl. Math., 154, No.3 (2006), 537-551.
%F 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.
%F 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
%t 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 *)
%Y Cf. A082158, A082161.
%Y Cf. A102098, A102400.
%K easy,nonn
%O 1,2
%A _Valery A. Liskovets_, Apr 09 2003
%E More terms from _Paul D. Hanna_, Jan 07 2005
|
