|
%I #16 Aug 29 2019 09:52:20
%S 1,7,133,5362,380093,42258384,6830081860,1520132414241,
%T 447309239576913,168599289097947589,79364534944804317166,
%U 45701029702436877135199,31642128418550547009710906,25960688434777959685891570936,24926392120419324125117256758595,27708074645788511889179577045508824
%N Deterministic completely defined initially connected acyclic automata with 3 inputs and n+1 transient unlabeled states including a unique state having all transitions to the absorbing state.
%C Coefficients T_2(n,k) form the array A082172. These automata have no nontrivial automorphisms (by states).
%H V. 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 V. 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) := d_3(n)/(n-1)! where d_3(n) := b_3(n, 1)-sum(binomial(n-1, j-1)*T_3(n-j, j+1)*d_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+1)^3-1)^(n-i)*T_3(i, k), i=0..n-1), n>0.
%t b[_, 0, _] = 1; b[k_, n_, r_] := b[k, n, r] = Sum[Binomial[n, t] (-1)^(n - t - 1) ((t + r + 1)^k - 1)^(n - t) b[k, t, r], {t, 0, n - 1}];
%t d3[n_] := d3[n] = b[3, n, 1] - Sum[Binomial[n - 1, j - 1] T3[n - j, j + 1] d3[j], {j, 1, n - 1}];
%t T3[0, _] = 1; T3[n_, k_] := T3[n, k] = Sum[Binomial[n, i] (-1)^(n - i - 1) ((i + k + 1)^3 - 1)^(n - i) T3[i, k], {i, 0, n - 1}];
%t a[n_] := If[n == 1, 1, d3[n - 1]/(n - 2)!];
%t Array[a, 20] (* _Jean-François Alcover_, Aug 29 2019 *)
%Y Cf. A082160, A082163, A082162.
%K easy,nonn
%O 1,2
%A _Valery A. Liskovets_, Apr 09 2003
%E More terms from _Jean-François Alcover_, Aug 29 2019
|
