A027834 -id:A027834 - cp's OEIS frontend

A006691 Normalized number of connected (n+1)-state finite automata with 2 inputs.

9, 148, 3493, 106431, 3950832, 172325014, 8617033285, 485267003023, 30363691715629, 2088698040637242, 156612539215405732, 12709745319947141220, 1109746209390479579732, 103724343230007402591558, 10332348604630683943445797, 1092720669631704348689818959, 122274820828415241343176467043

Offset: 1

N. J. A. Sloane

nonn

Is this sequence essentially the same as A304312? - Paul D. Hanna, May 11 2018
From Petros Hadjicostas, Feb 26 2021: (Start)
See Table 2 (p. 683) in Robinson (1984) for values of S(p)/(p-1)! = S(p,d)/(p-1)! with p >= 2 and d = 2. In the paper, S(p) = S(p,d) is the number of (labeled) strongly connected finite automata with state set {1, 2, ..., p} and d inputs (p. 680). Since the offset here is 1, the original name of the sequence was changed to read "(n+1)-state" from "n-state".
This change agrees with Valery A. Liskovets's formula below, who was the first one to derive expressions for the quantity S(p) = S(p,d) for a general d more than a decade before Robinson (1984). See Liskovets (1971), where S(p) = S(p,d), with d inputs, is denoted by sigma_r(n) with r = d (inputs) and n = p (number of states). For d = 2, the values of S(p) = S(p,d=2) = (p-1)!*a(p-1) for p >= 1 (with a(0) := 1) are given in A027834, which has the correct name.
We may suggest two possible names for a(n): (i) the normalized number of labeled strongly connected (n+1)-state finite automata with 2 inputs, or (ii) the number of unlabeled strongly connected (n+1)-state finite automata with 2 inputs and a starting gate. (For purely unlabeled strongly connected n-state finite automata with 2 inputs, see A027835, whose terms are calculated based on Valery A. Liskovets' formulas.) (End)

Robert W. Robinson, Counting strongly connected finite automata, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651 (86g:05026).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Hugo Pfoertner, Table of n, a(n) for n = 1..200
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).
R. W. Robinson, Counting strongly connected finite automata, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651. (86g:05026). [Annotated scanned copy, with permission of the author.]

Cf. A027834, A304312.

v[r_, n_] := 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_] := s[r, n] = v[r, n] + Sum[Binomial[n - 1, t - 1] * v[r, n - t] * s[r, t], {t, 1, n - 1}]
A027834[n_] := s[2, n];
a[n_] := A027834[n + 1]/n!;
Array[a, 28] (* Jean-François Alcover, Aug 27 2019 *)

a(n) = A027834(n+1)/n!. - Valery A. Liskovets, May 21 2018

Extended using the formula by Valery A. Liskovets by Hugo Pfoertner, May 21 2018

Name edited by Petros Hadjicostas, Feb 26 2021 to agree with Robinson's and Liskovets' papers.

A342202 T(n,k) = V(n,k)/k!, where V(n,k) = k^(nk) - Sum_{t=1..k-1} binomial(k,t)k^(n(k-t))V(n,t) for n, k >= 1; square array T read by upwards antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 4, 0, 1, 24, 45, 0, 1, 112, 2268, 816, 0, 1, 480, 76221, 461056, 20225, 0, 1, 1984, 2245320, 152978176, 160977375, 632700, 0, 1, 8064, 62858025, 43083161600, 673315202500, 85624508376, 23836540, 0, 1, 32512, 1723364748, 11442561314816, 2331513459843750, 5508710472669120, 64363893844726, 1048592640, 0

Offset: 1

Petros Hadjicostas, Mar 04 2021

To prove Paul D. Hanna's formula for the row n o.g.f. A(x,n) = Sum_{m >= 1} T(n,m)*x^m, we use Leibniz's rule for the k-th derivative of a product of functions: dx^k(exp(k^n*x) * (1 - A(x,n)))/dx = Sum_{s=0..k} binomial(k,s) * d^s(exp(k^n*x))/dx^s * d^(k-s) (1 - A(x,n))/dx^(k-s) = k^(n*k) * exp(k^n*x) * (1 - Sum_{m>=1} T(n,m) * x^m) - Sum_{s=0..k-1} binomial(k,s) * k^(n*s) * exp(k^n*x) * (Sum_{m>=1} (m!/(m-(k-s))!) * T(n,m) * x^(m-(k-s))). The coefficient of x^k for exp(k^n*x) * (1 - A(x,n)) is obtained by setting x = 0 in the k-the derivative, and it is equal to k^(n*k) - Sum_{s=0..k-1} binomial(k,s) * k^(n*s) * (k-s)! * T(n,k-s) = k! * (k^(n*k)/k! - Sum_{s=0..k-1} k^(n*s)/s! * T(n,k-s)) = 0 because of the recurrence that T(n,k) satisfies.
To prove the formula below for T(n,k) that involves the compositions of k, we use mathematical induction on k. For k = 1, it is obvious. Assume it is true for all n and all m < k. Consider the compositions of k.
There is only one of size r = 1, namely k, and corresponds to the term k^(n*k)/k! in the recurrence T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s).
For the other compositions (s_1, ..., s_r) of k (of any size r >= 2), we group them according to the their last element s_r = s in {1, 2, ..., k - 1}, which gives rise to the factor k^(n*s)/s! = (Sum_{i=1..r} s_i)^(n*s_r)/s_r!. Using the inductive hypothesis, we substitute the expression for T(n,k-s) in the recurrence T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s). Each term in the expression for T(n,k-s) corresponds to a composition of k - s and is postmultiplied by k^(n*s)/s! = (Sum_{i=1..r} s_i)^(n*s_r)/s_r!. We thus get a term in the expression for T(n,k) that corresponds to a composition of the form (composition of k - s) + s, and the sign of this term is (-1)^((size of composition of k - s) + 1). The rest of the proof follows easily.

			Square array T(n,k) (n, k >= 1) begins:
  1,    0,        0,              0,                   0, ...
  1,    4,       45,            816,               20225, ...
  1,   24,     2268,         461056,           160977375, ...
  1,  112,    76221,      152978176,        673315202500, ...
  1,  480,  2245320,    43083161600,    2331513459843750, ...
  1, 1984, 62858025, 11442561314816, 7570813415735296875, ...
  ...

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).
Michel Marcus, PARI program that implements the formula for T(n,k) that involves compositions of k, 2021.
Robert W. Robinson, Counting strongly connected finite automata, in: Graph Theory with Applications to Graph Theory and Computer Science, Wiley, 1985, pp. 671-685.

Cf. A027834, A027835, A059153 (shifted column 2), A342405 (column 3).

Shifted rows: A000007 (row 1), A107668 (row 2), A107675 (row 3), A304394 (row 4), A304395 (row 5).

/* The recurrence for V(n,k) is due to Valery A. Liskovets. See his 1971 paper. A second program that implements the formula above involving the compositions of k appears in the links and was written by Michel Marcus. */
V(n,k) = k^(n*k) - sum(t=1, k-1, binomial(k, t)*k^(n*(k-t))*V(n,t));
T(n,k) = V(n,k)/k!

T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s).
For each n >= 1, the row n o.g.f. A(x,n) = Sum_{k >= 1} T(n,k)*x^k satisfies [x^k] (exp(k^n*x) * (1 - A(x,n))) = 0 for each k >= 1. (This is Paul D. Hanna's formula from the shifted rows 2-5: A107668, A107675, A304394, A304395.)
A027834(k) = T(2, k)*k! + Sum_{t=1..k-1} binomial(k-1, t-1) * T(2, k-t) * (k-t)! * A027834(t), where A027834(k) = number of strongly connected k-state 2-input automata. (See Theorem 2 in Valery A. Liskovets's 1971 paper.)
T(n,k) = Sum_{r=1..k} (-1)^(r-1) * Sum_{s_1, ..., s_r} (1/(Product_{j=1..r} s_j!)) * Product_{j=1..r} (Sum_{i=1..j} s_i)^(n*s_j)), where the second sum is over lists (s_1, ..., s_r) of positive integers s_i such that Sum_{i=1..r} s_i = k. (Thus the second sum is over all ordered partitions (i.e., compositions) of k.)
T(n,k=1) = 1 and T(n,k=2) = 2^n*(2^(n-1) - 1) = A059153(n-2) (with A059153(-1) := 0).
T(n,k=3) = (27^n - 3*9^n - 3*12^n)/6 + 6^n.
T(n,k=4) = 256^n/24 - (5/12)*64^n - 108^n/6 + 32^n/2 + 36^n/2 + 48^n/2 - 24^n.

A054746 Number of nonisomorphic connected binary n-state automata without output under input permutations.

Original entry on oeis.org

1, 6, 67, 1379, 40000, 1488212, 66468616, 3459744878, 205517092374, 13719689837415, 1016860316477931, 82855990193202263, 7361905026684383986, 708398087768889272827, 73390382551302560225067, 8144731151602797676232825, 963990026196934640329291135

Offset: 1

Vladeta Jovovic, Apr 22 2000

nonn

Inverse Euler transform of A054745.

			There are 40000 nonisomorphic connected binary 5-state automata under input permutations.

F. Harary and E. Palmer, Graphical Enumeration, 1973.

Alois P. Heinz, Table of n, a(n) for n = 1..45
M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, 1965, p. 110.

Cf. A054732, A027834.

More terms from Alois P. Heinz, Feb 20 2017

A006692 Number of connected n-state finite automata with 3 inputs.

Original entry on oeis.org

49, 6877, 1854545, 807478656, 514798204147, 451182323794896, 519961864703259753, 762210147961330421167, 1384945048774500147047194, 3055115321627096660341307614, 8043516699726480852467167758419, 24915939138210507189761922944830006, 89709850983809128394441772076036629240

Offset: 1

N. J. A. Sloane

nonn

Is this sequence essentially the same as A304313? - Paul D. Hanna, May 11 2018

Robert W. Robinson, Counting strongly connected finite automata, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651 (86g:05026).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Hugo Pfoertner, Table of n, a(n) for n = 1..200
R. W. Robinson, Counting strongly connected finite automata, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651. (86g:05026). [Annotated scanned copy, with permission of the author.]

Cf. A027834, A006691, A304313.

Extended using the PARI program by Paul D. Hanna in A027834 by Hugo Pfoertner, May 22 2018

A027835 Number of unlabeled strongly connected n-state 2-input automata.

Original entry on oeis.org

1, 6, 52, 892, 21291, 658885, 24617866, 1077142765, 53918557215, 3036369842197, 189881640057942, 13051044976503663, 977672716919010876, 79267586388173032966, 6914956215333832011058, 645771787789692953182732, 64277686448923785217048191, 6793045601578652098886514581, 759656437858515775195264228768, 89619947709601175930862298926038

Offset: 1

N. J. A. Sloane

nonn

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

Cf. A006689, 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) ))}
{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

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

cp's OEIS Frontend

A006691 Normalized number of connected (n+1)-state finite automata with 2 inputs.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A342202 T(n,k) = V(n,k)/k!, where V(n,k) = k^(n*k) - Sum_{t=1..k-1} binomial(k,t)*k^(n*(k-t))*V(n,t) for n, k >= 1; square array T read by upwards antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A054746 Number of nonisomorphic connected binary n-state automata without output under input permutations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A006692 Number of connected n-state finite automata with 3 inputs.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A027835 Number of unlabeled strongly connected n-state 2-input automata.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A342202 T(n,k) = V(n,k)/k!, where V(n,k) = k^(nk) - Sum_{t=1..k-1} binomial(k,t)k^(n(k-t))V(n,t) for n, k >= 1; square array T read by upwards antidiagonals.