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

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

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..200
• 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.]

Crossrefs

Cf. A027834, A304312.

Programs

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

Formula

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

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.