A027834 - OEIS

%I #28 Feb 27 2021 05:36:16

%S 1,9,296,20958,2554344,474099840,124074010080,43429847756400,

%T 19565965561887360,11018376449767451520,7579467449864423769600,

%U 6251471405353507523097600,6087988343847192559805952000,6910412728595671664966422425600,9042510998634333921282477985689600

%N Number of labeled strongly connected n-state 2-input automata.

%H Michael A. Harrison, <a href="https://doi.org/10.4153/CJM-1965-010-9">A census of finite automata</a>, Canadian Journal of Mathematics, 17 (1965), 100-113.

%H Valery A. Liskovets [ Liskovec ], <a href="https://www.researchgate.net/publication/268532943_Enumeration_of_non-isomorphic_strongly_connected_automata">Enumeration of nonisomorphic strongly connected automata</a>, (in Russian); Vesti Akad. Nauk. Belarus. SSR, Ser. Phys.-Mat., No. 3, 1971, pp. 26-30, esp. p. 30 (Math. Rev. 46 #5081; <a href="https://www.zbmath.org/?q=an%3A0224.94053">Zentralblatt 224 #94053</a>).

%H Valery A. Liskovets [ Liskovec ], <a href="https://www.researchgate.net/publication/246994823_ON_A_GENERAL_ENUMERATIVE_SCHEME_FOR_LABELED_GRAPHS">A general enumeration scheme for labeled graphs</a>, (in Russian); Dokl. Akad. Nauk. Belarus. SSR, Vol. 21, No. 6 (1977), pp. 496-499 (Math. Rev. 58 #21797; <a href="https://www.zbmath.org/?q=an%3A0412.05052">Zentralblatt 412 #05052</a>).

%H Robert W. Robinson, <a href="https://oeis.org/A006689/a006689_1.pdf">Counting strongly connected finite automata</a>, in: Graph Theory with Applications to Graph Theory and Computer Science, Wiley, 1985, pp. 671-685.

%F 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]

%t 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}]];

%t s[r_, n_] := v[r, n] + Sum[Binomial[n - 1, t - 1] * v[r, n - t] * s[r, t], {t, 1, n - 1}];

%t a[n_] := s[2, n];

%t Array[a, 15] (* _Jean-François Alcover_, Aug 27 2019, from PARI *)

%o (PARI) /* a(n) = s_2(n) using a formula (Th.2) of Valery Liskovets: */

%o {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) ))}

%o {s(r,n) = v(r,n) + sum(t=1,n-1, binomial(n-1,t-1) * v(r,n-t) * s(r,t) )}

%o for(n=1,20,print1( s(r=2, n),", ")) \\ _Paul D. Hanna_, May 16 2018

%Y Cf. A006689, A006691, A027835.

%K nonn

%O 1,2

%A _N. J. A. Sloane_.

%E Sequence extended (a(7)-a(15)) by _Paul D. Hanna_ using a formula by _Valery A. Liskovets_.