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

Author

N. J. A. Sloane

Keywords

• nonn

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

Crossrefs

Cf. A006689, A027834.

Programs

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

Extensions

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