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).
PROG
(PARI) {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) )} \\ This is Paul D. Hanna's PARI program from A027834 regarding s(r, n) = number of labeled strongly connected n-state r-input automata.
{SS(r, n) = (1/n)*sumdiv(n, m, (s(r, m)/(m-1)!)*sumdiv(n/m, d, moebius(n/(m*d))*d^((r-1)*m+1)))} \\ This calculates the number of unlabeled strongly connected n-state r-input automata. It is Valery A. Liskovets's formula from his 1971 paper.
for(n=1, 20, print1( SS(r=2, n), ", ")) \\ Petros Hadjicostas, Feb 26 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from Petros Hadjicostas, Feb 26 2021 using formula (5), p. 28, in Liskovets (1971)
STATUS
approved