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,2

Links

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

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.

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]

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

Prog

(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

Crossrefs

Cf. A006689, A006691, A027835.

Sequence in context: A053935 A332129 A086699 * A175823 A129934 A003303

Adjacent sequences: A027831 A027832 A027833 * A027835 A027836 A027837

Keyword

nonn

Author

N. J. A. Sloane.

Extensions

Sequence extended (a(7)-a(15)) by Paul D. Hanna using a formula by Valery A. Liskovets.

Status

approved