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

9, 148, 3493, 106431, 3950832, 172325014, 8617033285, 485267003023, 30363691715629, 2088698040637242, 156612539215405732, 12709745319947141220, 1109746209390479579732, 103724343230007402591558

Offset

1,1

Comments

Is this sequence essentially the same as A304312? - Paul D. Hanna, May 11 2018

From Petros Hadjicostas, Feb 26 2021: (Start)

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".

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.

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)

References

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).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Hugo Pfoertner, Table of n, a(n) for n = 1..28

Valery A. Liskovets [ Liskovec ], Enumeration of nonisomorphic strongly connected automata, (in Russian); Vesti Akad. Nauk. Belarus. SSR, Ser. Phys.-Mat., No. 3, 1971, pp. 26-30, esp. p. 30 (Math. Rev. 46 #5081; Zentralblatt 224 #94053).

Valery A. Liskovets [ Liskovec ], A general enumeration scheme for labeled graphs, (in Russian); Dokl. Akad. Nauk. Belarus. SSR, Vol. 21, No. 6 (1977), pp. 496-499 (Math. Rev. 58 #21797; Zentralblatt 412 #05052).

R. 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). [Annotated scanned copy, with permission of the author.]

Formula

a(n) = A027834(n+1)/n!. - Valery A. Liskovets, May 21 2018

Mathematica

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}]];
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}]
A027834[n_] := s[2, n];
a[n_] := A027834[n + 1]/n!;
Array[a, 28] (* Jean-François Alcover, Aug 27 2019 *)

Crossrefs

Cf. A027834, A304312.

Sequence in context: A241797 A222439 A211106 * A304312 A361066 A050580

Adjacent sequences: A006688 A006689 A006690 * A006692 A006693 A006694

Keyword

nonn

Author

N. J. A. Sloane.

Extensions

Extended using the formula by Valery A. Liskovets by Hugo Pfoertner, May 21 2018

Name edited by Petros Hadjicostas, Feb 26 2021 to agree with Robinson's and Liskovets' papers.

Status

approved