|
|
A006691
|
|
Normalized number of connected (n+1)-state finite automata with 2 inputs.
(Formerly M4662)
|
|
7
|
|
|
9, 148, 3493, 106431, 3950832, 172325014, 8617033285, 485267003023, 30363691715629, 2088698040637242, 156612539215405732, 12709745319947141220, 1109746209390479579732, 103724343230007402591558
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
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
|
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
|
|
|
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}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Name edited by Petros Hadjicostas, Feb 26 2021 to agree with Robinson's and Liskovets' papers.
|
|
STATUS
|
approved
|
|
|
|