OFFSET
1,2
LINKS
Michael A. Harrison, A census of finite automata, Canadian Journal of Mathematics, 17 (1965), 100-113.
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).
Robert W. Robinson, Counting strongly connected finite automata, in: Graph Theory with Applications to Graph Theory and Computer Science, Wiley, 1985, pp. 671-685.
FORMULA
a(n) = A006691(n-1)*(n-1)! for n >= 1 (with A006691(0) := 1). [This is a restatement of Valery A. Liskovets' formula in A006691. The original name of A006691 was edited accordingly. - Petros Hadjicostas, Feb 26 2021]
MATHEMATICA
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_] := v[r, n] + Sum[Binomial[n - 1, t - 1] * v[r, n - t] * s[r, t], {t, 1, n - 1}];
a[n_] := s[2, n];
Array[a, 15] (* Jean-François Alcover, Aug 27 2019, from PARI *)
PROG
(PARI) /* a(n) = s_2(n) using a formula (Th.2) of Valery Liskovets: */
{v(r, n) = if(n==0, 1, n^(r*n) - sum(t=1, n-1, binomial(n, t) * n^(r*(n-t)) * v(r, t) ))}
{s(r, n) = v(r, n) + sum(t=1, n-1, binomial(n-1, t-1) * v(r, n-t) * s(r, t) )}
for(n=1, 20, print1( s(r=2, n), ", ")) \\ Paul D. Hanna, May 16 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
Sequence extended (a(7)-a(15)) by Paul D. Hanna using a formula by Valery A. Liskovets.
STATUS
approved