cp's OEIS Frontend

A006690 Number of deterministic, completely-defined, initially-connected finite automata with 3 inputs and n unlabeled states.

%I A006690 M5316 #67 Mar 08 2021 22:29:51
%S A006690 1,56,7965,2128064,914929500,576689214816,500750172337212,
%T A006690 572879126392178688,835007874759393878655,1510492370204314777345000,
%U A006690 3320470273536658970739763334,8718034433102107344888781813632,26945647825926481227016730431025962,96843697086370972449408988324175689680
%N A006690 Number of deterministic, completely-defined, initially-connected finite automata with 3 inputs and n unlabeled states.
%C A006690 a(n) is divisible by n^3, see A082168. These automata have no nontrivial automorphisms (by states).
%C A006690 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 A006690 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 A006690 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 A006690 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 A006690 V. A. Liskovets, The number of initially connected automata, Kibernetika, (Kiev), No3 (1969), 16-19; Engl. transl.: Cybernetics, v.4 (1969), 259-262.
%D A006690 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 A006690 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006690 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 A006690 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 A006690 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 A006690 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 A006690 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 A006690 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 A006690 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 A006690 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 A006690 b := proc(k,n)
%p A006690     option remember;
%p A006690     if n = 1 then
%p A006690         1;
%p A006690     else
%p A006690         n^(k*n) -add(binomial(n-1,j-1)*n^(k*(n-j))*procname(k,j),j=1..n-1) ;
%p A006690     end if;
%p A006690 end proc:
%p A006690 B := proc(k,n)
%p A006690     b(k,n)/(n-1)! ;
%p A006690 end proc:
%p A006690 A006690 := proc(n)
%p A006690     B(3,n) ;
%p A006690 end proc:
%p A006690 seq(A006690(n),n=1..10) ; # _R. J. Mathar_, May 21 2018
%t A006690 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 A006690 (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 A006690 (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 A006690 Cf. A006689, A006689, A107671, A107676.
%K A006690 easy,nonn
%O A006690 1,2
%A A006690 _N. J. A. Sloane_
%E A006690 a(11) and more detailed definition from _Valery A. Liskovets_, Apr 09 2003
%E A006690 Edited by _N. J. A. Sloane_, Dec 06 2008 at the suggestion of _R. J. Mathar_
%E A006690 More terms from _M. F. Hasler_, May 16 2018