|
%I M4876 #69 Mar 11 2021 02:46:07
%S 1,12,216,5248,160675,5931540,256182290,12665445248,705068085303,
%T 43631250229700,2970581345516818,220642839342906336,
%U 17753181687544516980,1538156947936524172656,142767837727544113783650
%N Number of deterministic, completely-defined, initially-connected finite automata with 2 inputs and n unlabeled states.
%C a(n) is divisible by n^2, see A082166. These automata have no nontrivial automorphisms (by states).
%C 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 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 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 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 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, 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 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 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 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 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 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 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 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 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 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 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 A006689 := proc(n)
%p B(2,n) ;
%p end proc:
%p seq(A006689(n),n=1..10) ; # _R. J. Mathar_, May 21 2018
%t 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 (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 (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 Cf. A006690, A107670, A107667.
%K easy,nonn
%O 1,2
%A _N. J. A. Sloane_
%E More terms and more detailed definition from _Valery A. Liskovets_, Apr 09 2003
%E Further terms from _Paul D. Hanna_, May 19 2005
%E Edited by _N. J. A. Sloane_, Dec 06 2008 at the suggestion of _R. J. Mathar_
|
