login
A082164
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.
2
1, 7, 133, 5362, 380093, 42258384, 6830081860, 1520132414241, 447309239576913, 168599289097947589, 79364534944804317166, 45701029702436877135199, 31642128418550547009710906, 25960688434777959685891570936, 24926392120419324125117256758595, 27708074645788511889179577045508824
OFFSET
1,2
COMMENTS
Coefficients T_2(n,k) form the array A082172. These automata have no nontrivial automorphisms (by states).
LINKS
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), 537-551.
FORMULA
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.
MATHEMATICA
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}];
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}];
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}];
a[n_] := If[n == 1, 1, d3[n - 1]/(n - 2)!];
Array[a, 20] (* Jean-François Alcover, Aug 29 2019 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Apr 09 2003
EXTENSIONS
More terms from Jean-François Alcover, Aug 29 2019
STATUS
approved