|
|
A082162
|
|
Number of deterministic completely defined initially connected acyclic automata with 3 inputs and n transient unlabeled states (and a unique absorbing state).
|
|
12
|
|
|
1, 7, 139, 5711, 408354, 45605881, 7390305396, 1647470410551, 485292763088275, 183049273155939442, 86211400693272461866
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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
|
|
|
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.
|
|
MATHEMATICA
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|