1,2

a(n) is divisible by n^3, see A082168. These automata have no nontrivial automorphisms (by states).

Found in column 0 of triangle A107676, which is the matrix cube of triangle A107671 (see recurrence formulas). - Paul D. Hanna (pauldhanna(AT)juno.com), Jun 07 2005

A complete initially connected deterministic finite automata (icdfa) with n states in an alphabet of k symbols can be represented by a special string of {0,...,n-1}^* with length kn. In that string, let be f_i be the index of the first occurrence of state i (used in the formula). - Nelma Moreira (nam(AT)ncc.up.pt), Jul 31 2005

V. A. Liskovets, The number of initially connected automata, Kibernetika, (Kiev), No3 (1969), 16-19; Engl. transl.: Cybernetics, v.4 (1969), 259-262.

V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.

R. Reis, N. Moreira and M. Almeida, On the Representation of Finite Automata, in Proocedings of 7th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS05) Jun 30, 2005, Como, Italy, page 269-276

M. Almeida, N. Moreira and R. Reis. On the Representation of Finite Automata, Technical Report DCC-2005-04, DCC - FC & LIACC, Universidade do Porto, April, 2005.

V. A. Liskovets, Exact enumeration of acyclic deterministic automata,Discrete Appl. Math., 154, No.3 (2006), 537-551.

a(n)=h_3(n)/(n-1)! where h_3(1) := 1, h_3(n) := n^(3*n)-sum(binomial(n-1, i-1)*n^(3*n-3*i)*h_3(i), i=1..n-1), n>1.

For k=3, a(n)= sum(prod(i=1..n-1, i^{f_i - f_{i-1} -1})*n^{n*k-f_{n-1}}) where the sum is taken over integers f_1, ..., f_{n-1} satisfying 0<= f_1 < k and f_{i-1}< f_{i} <i*k for i = 2..n-1 - Nelma Moreira (nam(AT)ncc.up.pt), Jul 31 2005

(PARI) {a(n)=local(P=matrix(n+1, n+1, r, c, if(r>=c, (r^3)^(r-c)/(r-c)!)), D=matrix(n+1, n+1, r, c, if(r==c, r))); (P^-1*D^3*P)[n+1, 1]} (Hanna)

Cf. A082165, A107671, A107676.

Adjacent sequences: A082164 A082165 A082166 this_sequence A082168 A082169 A082170

Sequence in context: A049033 A009600 A006690 this_sequence A034204 A091546 A059989

easy,nonn

Valery Liskovets (liskov(AT)im.bas-net.by), Apr 09 2003