cp's OEIS Frontend

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

%I A006689 M4876 #72 Aug 14 2025 09:10:58
%S A006689 1,12,216,5248,160675,5931540,256182290,12665445248,705068085303,
%T A006689 43631250229700,2970581345516818,220642839342906336,
%U A006689 17753181687544516980,1538156947936524172656,142767837727544113783650,14132742269814671677890048,1486239549269418316509918111,165468157149718534883789004804
%N A006689 Number of deterministic, completely-defined, initially-connected finite automata with 2 inputs and n unlabeled states.
%C A006689 a(n) is divisible by n^2, see A082166. These automata have no nontrivial automorphisms (by states).
%C A006689 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_, May 19 2005
%C A006689 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
%D A006689 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 A006689 V. A. Liskovets, The number of initially connected automata, Kibernetika, (Kiev), No3 (1969), 16-19; Engl. transl.: Cybernetics, v.4 (1969), 259-262.
%D A006689 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 A006689 Robert W. Robinson, Counting strongly connected finite automata, 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).
%D A006689 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006689 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 A006689 M. Almeida, N. Moreira, and 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, B(k=2,n)
%H A006689 E. Lebensztayn, <a href="http://arxiv.org/abs/1411.5614">A large deviations principle for the Maki-Thompson rumour model</a>, arXiv preprint arXiv:1411.5614 [math.PR], 2014-2015.
%H A006689 V. A. Liskovets, <a href="https://www.researchgate.net/publication/245012762_The_number_of_connected_initial_automata">The number of initially connected automata</a>, Kibernetika, (Kiev), No3 (1969), 16-19; Engl. transl.: Cybernetics, v.4 (1969), 259-262.
%H A006689 V. 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 A006689 V. 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 A006689 R. 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.]
%H A006689 G. Sedlitz, <a href="https://dmg.tuwien.ac.at/bgitten/Theses/sedlitz.pdf">Abzahlung von Automaten, formalen Sprachen und verwandten Strukturen</a>, Master's Thesis, Vienna (2017), Theorem 6.1
%F A006689 a(n) = h_2(n)/(n-1)!, where h_2(1) := 1, h_2(n) := n^(2*n) - Sum_{i=1..n-1} binomial(n-1, i-1)*n^(2*n-2*i)*h_2(i) for n > 1.
%F A006689 For k = 2, 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_, Feb 26 2021. See Theorem 8 in Almeida, Moreira, and Reis (2007). The value of f_0 is not relevant.]
%e A006689 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).
%p A006689 b := proc(k,n)
%p A006689     option remember;
%p A006689     if n = 1 then
%p A006689         1;
%p A006689     else
%p A006689         n^(k*n) -add(binomial(n-1,j-1)*n^(k*(n-j))*procname(k,j),j=1..n-1) ;
%p A006689     end if;
%p A006689 end proc:
%p A006689 B := proc(k,n)
%p A006689     b(k,n)/(n-1)! ;
%p A006689 end proc:
%p A006689 A006689 := proc(n)
%p A006689     B(2,n) ;
%p A006689 end proc:
%p A006689 seq(A006689(n),n=1..10) ; # _R. J. Mathar_, May 21 2018
%t A006689 a[1] = 1; a[n_] := a[n] = n^(2*n)/(n-1)! - Sum[n^(2*(n-i))*a[i]/(n-i)!, {i, 1, n-1}]; Table[ a[n], {n, 1, 15}] (* _Jean-François Alcover_, Dec 15 2014 *)
%o A006689 (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)))
%o A006689 (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))
%Y A006689 Cf. A006690, A107670, A107667.
%K A006689 easy,nonn
%O A006689 1,2
%A A006689 _N. J. A. Sloane_
%E A006689 More terms and more detailed definition from _Valery A. Liskovets_, Apr 09 2003
%E A006689 Further terms from _Paul D. Hanna_, May 19 2005
%E A006689 Edited by _N. J. A. Sloane_, Dec 06 2008 at the suggestion of _R. J. Mathar_