A027834 Number of labeled strongly connected n-state 2-input automata.
1, 9, 296, 20958, 2554344, 474099840, 124074010080, 43429847756400, 19565965561887360, 11018376449767451520, 7579467449864423769600, 6251471405353507523097600, 6087988343847192559805952000, 6910412728595671664966422425600, 9042510998634333921282477985689600
Offset: 1
Keywords
Links
- Hugo Pfoertner, Table of n, a(n) for n = 1..200
- 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.
Programs
-
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 *) -
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
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]
Extensions
Sequence extended (a(7)-a(15)) by Paul D. Hanna using a formula by Valery A. Liskovets.