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.

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

Table of n, a(n) for n=1..16.

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

Cf. A082160, A082163, A082162.

Sequence in context: A274788 A274258 A251577 * A229464 A317216 A119670

Adjacent sequences: A082161 A082162 A082163 * A082165 A082166 A082167

Keyword

easy,nonn

Author

Valery A. Liskovets, Apr 09 2003

Extensions

More terms from Jean-François Alcover, Aug 29 2019

Status

approved