login
Normalized number of connected (n+1)-state finite automata with 2 inputs.
(Formerly M4662)
7

%I M4662 #54 Feb 27 2021 11:00:52

%S 9,148,3493,106431,3950832,172325014,8617033285,485267003023,

%T 30363691715629,2088698040637242,156612539215405732,

%U 12709745319947141220,1109746209390479579732,103724343230007402591558

%N Normalized number of connected (n+1)-state finite automata with 2 inputs.

%C Is this sequence essentially the same as A304312? - _Paul D. Hanna_, May 11 2018

%C From _Petros Hadjicostas_, Feb 26 2021: (Start)

%C See Table 2 (p. 683) in Robinson (1984) for values of S(p)/(p-1)! = S(p,d)/(p-1)! with p >= 2 and d = 2. In the paper, S(p) = S(p,d) is the number of (labeled) strongly connected finite automata with state set {1, 2, ..., p} and d inputs (p. 680). Since the offset here is 1, the original name of the sequence was changed to read "(n+1)-state" from "n-state".

%C This change agrees with _Valery A. Liskovets_'s formula below, who was the first one to derive expressions for the quantity S(p) = S(p,d) for a general d more than a decade before Robinson (1984). See Liskovets (1971), where S(p) = S(p,d), with d inputs, is denoted by sigma_r(n) with r = d (inputs) and n = p (number of states). For d = 2, the values of S(p) = S(p,d=2) = (p-1)!*a(p-1) for p >= 1 (with a(0) := 1) are given in A027834, which has the correct name.

%C We may suggest two possible names for a(n): (i) the normalized number of labeled strongly connected (n+1)-state finite automata with 2 inputs, or (ii) the number of unlabeled strongly connected (n+1)-state finite automata with 2 inputs and a starting gate. (For purely unlabeled strongly connected n-state finite automata with 2 inputs, see A027835, whose terms are calculated based on _Valery A. Liskovets_' formulas.) (End)

%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 Hugo Pfoertner, <a href="/A006691/b006691.txt">Table of n, a(n) for n = 1..28</a>

%H Valery A. Liskovets [ Liskovec ], <a href="https://www.researchgate.net/publication/268532943_Enumeration_of_non-isomorphic_strongly_connected_automata">Enumeration of nonisomorphic strongly connected automata</a>, (in Russian); Vesti Akad. Nauk. Belarus. SSR, Ser. Phys.-Mat., No. 3, 1971, pp. 26-30, esp. p. 30 (Math. Rev. 46 #5081; <a href="https://www.zbmath.org/?q=an%3A0224.94053">Zentralblatt 224 #94053</a>).

%H Valery A. Liskovets [ Liskovec ], <a href="https://www.researchgate.net/publication/246994823_ON_A_GENERAL_ENUMERATIVE_SCHEME_FOR_LABELED_GRAPHS">A general enumeration scheme for labeled graphs</a>, (in Russian); Dokl. Akad. Nauk. Belarus. SSR, Vol. 21, No. 6 (1977), pp. 496-499 (Math. Rev. 58 #21797; <a href="https://www.zbmath.org/?q=an%3A0412.05052">Zentralblatt 412 #05052</a>).

%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.]

%F a(n) = A027834(n+1)/n!. - _Valery A. Liskovets_, May 21 2018

%t v[r_, n_] := v[r, n] = If[n == 0, 1, n^(r*n) - Sum[Binomial[n, t] * n^(r*(n - t)) * v[r, t] , {t, 1, n - 1}]];

%t s[r_, n_] := s[r, n] = v[r, n] + Sum[Binomial[n - 1, t - 1] * v[r, n - t] * s[r, t], {t, 1, n - 1}]

%t A027834[n_] := s[2, n];

%t a[n_] := A027834[n + 1]/n!;

%t Array[a, 28] (* _Jean-François Alcover_, Aug 27 2019 *)

%Y Cf. A027834, A304312.

%K nonn

%O 1,1

%A _N. J. A. Sloane_.

%E Extended using the formula by _Valery A. Liskovets_ by _Hugo Pfoertner_, May 21 2018

%E Name edited by _Petros Hadjicostas_, Feb 26 2021 to agree with Robinson's and Liskovets' papers.