A027835 Number of unlabeled strongly connected n-state 2-input automata.

1, 6, 52, 892, 21291, 658885, 24617866, 1077142765, 53918557215, 3036369842197, 189881640057942, 13051044976503663, 977672716919010876, 79267586388173032966, 6914956215333832011058, 645771787789692953182732, 64277686448923785217048191, 6793045601578652098886514581, 759656437858515775195264228768, 89619947709601175930862298926038

Offset

1,2

Links

Table of n, a(n) for n=1..20.

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

Cf. A006689, A027834.

Sequence in context: A097820 A166889 A164894 * A055973 A223345 A362907

Adjacent sequences: A027832 A027833 A027834 * A027836 A027837 A027838

Keyword

nonn

Author

N. J. A. Sloane.

Extensions

More terms from Petros Hadjicostas, Feb 26 2021 using formula (5), p. 28, in Liskovets (1971)

Status

approved