|
%I M5316 #67 Mar 08 2021 22:29:51
%S 1,56,7965,2128064,914929500,576689214816,500750172337212,
%T 572879126392178688,835007874759393878655,1510492370204314777345000,
%U 3320470273536658970739763334,8718034433102107344888781813632,26945647825926481227016730431025962,96843697086370972449408988324175689680
%N Number of deterministic, completely-defined, initially-connected finite automata with 3 inputs and n unlabeled states.
%C a(n) is divisible by n^3, see A082168. These automata have no nontrivial automorphisms (by states).
%C Found in column 0 of triangle A107676, which is the matrix cube of triangle A107671 (see recurrence formulas). - _Paul D. Hanna_, Jun 07 2005
%C A complete initially connected deterministic finite automaton (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 f_i be the index of the first occurrence of state i (used in the formula). - _Nelma Moreira_, Jul 31 2005
%C This is H_3(n) in Liskovets (DAM, Vol. 154, 2006), p. 548; the formula for H_k is given in Eq. (11), p. 546. - _M. F. Hasler_, May 16 2018
%D R. Bacher and 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.
%D V. A. Liskovets, The number of initially connected automata, Kibernetika, (Kiev), No3 (1969), 16-19; Engl. transl.: Cybernetics, v.4 (1969), 259-262.
%D 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
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H M. Almeida, N. Moreira and R. Reis, <a href="http://www.dcc.fc.up.pt/Pubs/TR05/dcc-2005-04.pdf">On the Representation of Finite Automata</a>, Technical Report DCC-2005-04, DCC - FC & LIACC, Universidade do Porto, April, 2005.
%H M. Almeida, N. Moreira, R. Reis, <a href="http://dx.doi.org/10.1016/j.tcs.2007.07.029">Enumeration and generation with a string automata representation</a>, Theor. Comp. Sci. 387 (2007), 93-102; see B(k=3,n).
%H Valery A. Liskovets, <a href="https://www.researchgate.net/publication/245012762_The_number_of_connected_initial_automata">The number of connected initial automata</a>, Kibernetika (Kiev), 3 (1969), 16-19 (in Russian; English translation: Cybernetics, 4 (1969), 259-262).
%H Valery A. Liskovets, <a href="http://igm.univ-mlv.fr/~fpsac/FPSAC03/ARTICLES/5.pdf">Exact enumeration of acyclic automata</a>, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
%H Valery A. Liskovets, <a href="http://dx.doi.org/10.1016/j.dam.2005.06.009">Exact enumeration of acyclic deterministic automata</a>, Discrete Appl. Math., 154, No. 3 (2006), 537-551.
%H Robert W. Robinson, <a href="/A006689/a006689_1.pdf">Counting strongly connected finite automata</a>, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651. (86g:05026). [Annotated scanned copy, with permission of the author.]
%F a(n) = h_3(n)/(n-1)!, where h_3(1) := 1, h_3(n) := n^(3*n) - Sum_{i=1..n-1} binomial(n-1, i-1) * n^(3*n-3*i) * h_3(i) for n > 1.
%F For k = 3, a(n) = Sum (Product_{i=1..n-1} i^(f_i - f_{i-1} - 1))) * n^(n*k - f_{n-1} - 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_, Jul 31 2005 [Typo corrected by _Petros Hadjicostas_, Mar 06 2021. See Theorem 8 in Almeida, Moreira, and Reis (2007). The value of f_0 is not relevant.]
%p b := proc(k,n)
%p option remember;
%p if n = 1 then
%p 1;
%p else
%p n^(k*n) -add(binomial(n-1,j-1)*n^(k*(n-j))*procname(k,j),j=1..n-1) ;
%p end if;
%p end proc:
%p B := proc(k,n)
%p b(k,n)/(n-1)! ;
%p end proc:
%p A006690 := proc(n)
%p B(3,n) ;
%p end proc:
%p seq(A006690(n),n=1..10) ; # _R. J. Mathar_, May 21 2018
%t a[1] = 1; a[n_] := a[n] = n^(3*n)/(n-1)! - Sum[n^(3*(n-i))*a[i]/(n-i)!, {i, 1, n-1}]; Table[a[n], {n, 1, 11}] (* _Jean-François Alcover_, Dec 15 2014 *)
%o (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]} \\ _Paul D. Hanna_, Jun 07 2005
%o (PARI) A6690=[1];A006690(n)={for(n=#A6690+1,n,A6690=concat(A6690,n^(3*n)/(n-1)!-sum(k=1,n-1,n^(3*k)*A6690[n-k]/k!)));A6690[n]} \\ _M. F. Hasler_, May 16 2018
%Y Cf. A006689, A006689, A107671, A107676.
%K easy,nonn
%O 1,2
%A _N. J. A. Sloane_
%E a(11) and more detailed definition from _Valery A. Liskovets_, Apr 09 2003
%E Edited by _N. J. A. Sloane_, Dec 06 2008 at the suggestion of _R. J. Mathar_
%E More terms from _M. F. Hasler_, May 16 2018
|
