cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A027834 #35 Aug 13 2025 10:19:36
%S A027834 1,9,296,20958,2554344,474099840,124074010080,43429847756400,
%T A027834 19565965561887360,11018376449767451520,7579467449864423769600,
%U A027834 6251471405353507523097600,6087988343847192559805952000,6910412728595671664966422425600,9042510998634333921282477985689600
%N A027834 Number of labeled strongly connected n-state 2-input automata.
%H A027834 Hugo Pfoertner, <a href="/A027834/b027834.txt">Table of n, a(n) for n = 1..200</a>
%H A027834 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 A027834 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 A027834 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 A027834 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 A027834 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 A027834 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 A027834 s[r_, n_] := v[r, n] + Sum[Binomial[n - 1, t - 1] * v[r, n - t] * s[r, t], {t, 1, n - 1}];
%t A027834 a[n_] := s[2, n];
%t A027834 Array[a, 15] (* _Jean-François Alcover_, Aug 27 2019, from PARI *)
%o A027834 (PARI) /* a(n) = s_2(n) using a formula (Th.2) of Valery Liskovets: */
%o A027834 {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 A027834 {s(r,n) = v(r,n) + sum(t=1,n-1, binomial(n-1,t-1) * v(r,n-t) * s(r,t) )}
%o A027834 for(n=1,20,print1( s(r=2, n),", ")) \\ _Paul D. Hanna_, May 16 2018
%Y A027834 Cf. A006689, A006691, A027835.
%K A027834 nonn
%O A027834 1,2
%A A027834 _N. J. A. Sloane_
%E A027834 Sequence extended (a(7)-a(15)) by _Paul D. Hanna_ using a formula by _Valery A. Liskovets_.