1,2

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

Equals the first column of triangle A107670, which is the matrix square of triangle A107667. As a lower triangular matrix T, A107667 satisfies: T = D + SHIFT_LEFT(T^2) where SHIFT_LEFT shifts each row 1 place left and D is the diagonal matrix [1,2,3,...]. - Paul D. Hanna (pauldhanna(AT)juno.com), May 19 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_2(n)/(n-1)! where h_2(1) := 1, h_2(n) := n^(2*n)-sum(binomial(n-1, i-1)*n^(2*n-2*i)*h_2(i), i=1..n-1), n>1.

For k=2, 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

a(2)=12 since the following transition diagrams represent all twelve initially connected automata with two input letters x and y and two states 1 (initial) and 2:

1==x,y==>2==>, 1--x-->2==>, 1--y-->2==>, 1--y-->1 1--x-->1

where the transitions from state 2 are specified arbitrary (4 different possibilities in every case).

(PARI) {a(n)=if(n<1, 0, n^(2*n)/(n-1)!-sum(i=1, n-1, n^(2*(n-i))/(n-i)!*a(i)))} (PARI) {a(n)=local(A); if(n<1, 0, A=n*x+x*O(x^n); for(k=0, n, A+=polcoeff(A, k)*x^k*(n-prod(i=0, k, 1-(n-i)*x))); polcoeff(A, n))}

Cf. A107670, A107667, A082167.

Sequence in context: A119309 A034788 A006689 this_sequence A009176 A087585 A098647

Adjacent sequences: A082162 A082163 A082164 this_sequence A082166 A082167 A082168

easy,nonn

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

More terms from Paul D. Hanna (pauldhanna(AT)juno.com), May 19 2005