A006691 -id:A006691 - cp's OEIS frontend

A304321 Table of coefficients in row functions F'(n,x)/F(n,x) such that [x^k] exp( k^n * x ) / F(n,x) = 0 for k>=1 and n>=1.

1, 1, 1, 1, 9, 1, 1, 49, 148, 1, 1, 225, 6877, 3493, 1, 1, 961, 229000, 1854545, 106431, 1, 1, 3969, 6737401, 612243125, 807478656, 3950832, 1, 1, 16129, 188580028, 172342090401, 3367384031526, 514798204147, 172325014, 1, 1, 65025, 5170118437, 45770504571813, 11657788116175751, 33056423981177346, 451182323794896, 8617033285, 1

Offset: 1

Paul D. Hanna, May 11 2018

Conjecture: T(n,k) in row n and column k gives the number of connected k-state finite automata with n inputs, for k>=0, for n>=1. For example, row 2 agrees with A006691, the number of connected n-state finite automata with 2 inputs; also, row 3 agrees with A006692, the number of connected n-state finite automata with 3 inputs.

			This table begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
1, 9, 148, 3493, 106431, 3950832, 172325014, 8617033285, 485267003023, ...;
1, 49, 6877, 1854545, 807478656, 514798204147, 451182323794896, ...;
1, 225, 229000, 612243125, 3367384031526, 33056423981177346, ...;
1, 961, 6737401, 172342090401, 11657788116175751, 1722786509653595220757, ...;
1, 3969, 188580028, 45770504571813, 37854124915368647781, ...;
1, 16129, 5170118437, 11889402239702065, 120067639589726126102806, ...;
1, 65025, 140510362000, 3061712634885743125, 377436820462509018320487276, ...;
1, 261121, 3804508566001, 785701359968473902401, 1182303741240112494973150131501, ...; ...
Let F'(n,x)/F(n,x) denote the o.g.f. of row n of this table, then the coefficient of x^k in exp(k^n*x)/F(n,x) = 0 for k>=1 and n>=1.

Paul D. Hanna, Table of n, a(n) for n = 1..1326 as a flattened table read by antidiagonals 1..51.

Cf. A304320, A304312 (row 2), A304313 (row 3), A304314 (row 4), A304315 (row 5).

m = 10(*rows*);
row[nn_] := Module[{F, s}, F = 1 + Sum[c[k] x^k, {k, m}]; s[n_] := Solve[ SeriesCoefficient[Exp[n^nn*x]/F, {x, 0, n}] == 0][[1]]; Do[F = F /. s[n], {n, m}]; CoefficientList[D[F, x]/F + O[x]^m, x]];
T = Array[row, m];
Table[T[[n-k+1, k]], {n, 1, m}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 27 2019 *)

{T(n,k) = my(A=[1],m); for(i=0, k, A=concat(A, 0); m=#A; A[m] = Vec( exp(x*(m-1)^n +x^2*O(x^m)) / Ser(A) )[m] ); L = Vec(Ser(A)'/Ser(A)); L[k+1]}
/* Print table: */
for(n=1,8, for(k=0,8, print1( T(n,k),", "));print(""))
/* Print as a flattened table: */
for(n=0,10, for(k=0,n, print1( T(n-k+1,k),", "));)

Row n of this table equals the logarithmic derivative of row n of table A304320.

For fixed row r > 1 is a(n) ~ sqrt(1-c) * r^(r*(n+1)) * n^((r-1)*n + r - 1/2) / (sqrt(2*Pi) * c^(n+1) * (r-c)^((r-1)*(n+1)) * exp((r-1)*n)), where c = -LambertW(-r*exp(-r)). - Vaclav Kotesovec, Aug 31 2020

A304322 O.g.f. A(x) satisfies: [x^n] exp( n^2 * x ) / A(x) = 0 for n>0.

Original entry on oeis.org

1, 1, 5, 54, 935, 22417, 685592, 25431764, 1106630687, 55174867339, 3097872254493, 193283918695494, 13260815963831108, 991928912663646012, 80325879518096889760, 7000127337189146831092, 653156403671376068448047, 64963788042207845593775999, 6861040250464949653809027311, 766815367797924824316405828466, 90417908118862070187113849296815

Offset: 0

Paul D. Hanna, May 11 2018

nonn

It is conjectured that the coefficients of o.g.f. A(x) consist entirely of integers.
Equals row 2 of table A304320.
O.g.f. A(x) = 1/(1 - x*B(x)), where B(x) is the o.g.f. of A107668.
Logarithmic derivative of o.g.f. A(x), A'(x)/A(x), equals o.g.f. of A304312.
Conjecture: given o.g.f. A(x), the coefficient of x^n in A'(x)/A(x) is the number of connected n-state finite automata with 2 inputs (A006691).

			O.g.f.: A(x) = 1 + x + 5*x^2 + 54*x^3 + 935*x^4 + 22417*x^5 + 685592*x^6 + 25431764*x^7 + 1106630687*x^8 + 55174867339*x^9 + 3097872254493*x^10 + ...
ILLUSTRATION OF DEFINITION.
The table of coefficients of x^k/k! in exp(n^2*x) / A(x) begins:
n=0: [1, -1, -8, -270, -19584, -2427000, -455544000, -120136161600, ...];
n=1: [1, 0, -9, -296, -20715, -2527704, -470405285, -123376631664, ...];
n=2: [1, 3, 0, -350, -24672, -2867256, -518870528, -133753337280, ...];
n=3: [1, 8, 55, 0, -29547, -3559056, -614943333, -153534305160, ...];
n=4: [1, 15, 216, 2674, 0, -4291704, -783235520, -187656684864, ...];
n=5: [1, 24, 567, 12880, 251541, 0, -948897125, -243358236600, ...];
n=6: [1, 35, 1216, 41634, 1372320, 38884296, 0, -295870371264, ...];
n=7: [1, 48, 2295, 109000, 5106453, 230531544, 8944955227, 0, ...];
n=8: [1, 63, 3960, 248050, 15443328, 949131144, 56257429312, 2865412167360, 0, ...]; ...
in which the main diagonal is all zeros after the initial term, illustrating that [x^n] exp( n^2*x ) / A(x) = 0 for n>=0.
LOGARITHMIC DERIVATIVE.
The logarithmic derivative of A(x) yields the o.g.f. of A304312:
A'(x)/A(x) = 1 + 9*x + 148*x^2 + 3493*x^3 + 106431*x^4 + 3950832*x^5 + 172325014*x^6 + 8617033285*x^7 + 485267003023*x^8 + 30363691715629*x^9 + ... + A304312(n)*x^n +...
INVERT TRANSFORM.
1/A(x) = 1 - x*B(x), where B(x) is the o.g.f. of A107668:
B(x) = 1 + 4*x + 45*x^2 + 816*x^3 + 20225*x^4 + 632700*x^5 + 23836540*x^6 + 1048592640*x^7 + 52696514169*x^8 + ... + A107668(n)*x^n + ...

Paul D. Hanna, Table of n, a(n) for n = 0..400

Cf. A304320, A304312, A304321, A304323, A304324, A304325.

Cf. A006691, A107668.

{a(n) = my(A=[1]); for(i=1, n, A=concat(A, 0); m=#A; A[m] = Vec( exp(x*(m-1)^2 +x*O(x^m)) / Ser(A) )[m] ); A[n+1]}
for(n=0,25, print1( a(n),", "))

a(n) ~ sqrt(1-c) * 2^(2*n - 1/2) * n^(n - 1/2) / (sqrt(Pi) * c^n * (2-c)^n * exp(n)), where c = -A226775 = -LambertW(-2*exp(-2)). - Vaclav Kotesovec, Aug 31 2020

A304312 Logarithmic derivative of F(x) that satisfies: [x^n] exp( n^2 * x ) / F(x) = 0 for n>0.

Original entry on oeis.org

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

Offset: 0

Paul D. Hanna, May 11 2018

nonn

Is this sequence essentially the same as A006691?
Conjecture: a(n) is the number of connected n-state finite automata with 2 inputs (A006691). [I believe the name of A006691 should be changed to read "(n+1)-state". See my comments in A006691. - Petros Hadjicostas, Feb 26 2021]
Equals row 2 of table A304321.

			O.g.f.: L(x) = 1 + 9*x + 148*x^2 + 3493*x^3 + 106431*x^4 + 3950832*x^5 + 172325014*x^6 + 8617033285*x^7 + 485267003023*x^8 + 30363691715629*x^9 + ...
such that L(x) = F'(x)/F(x) where F(x) is the o.g.f. of A304322 :
F(x) = 1 + x + 5*x^2 + 54*x^3 + 935*x^4 + 22417*x^5 + 685592*x^6 + 25431764*x^7 + 1106630687*x^8 + 55174867339*x^9 + 3097872254493*x^10 + ... + A304322(n)*x^n + ...
which satisfies [x^n] exp( n^2 * x ) / F(x) = 0 for n>0.

Paul D. Hanna, Table of n, a(n) for n = 0..400

Cf. A304322, A006691, A304321, A304313, A304314, A304315.

m = 25;
F = 1 + Sum[c[k] x^k, {k, m}];
s[n_] := Solve[SeriesCoefficient[Exp[n^2 * x]/F, {x, 0, n}] == 0][[1]];
Do[F = F /. s[n], {n, m}];
CoefficientList[D[F, x]/F + O[x]^m, x] (* Jean-François Alcover, May 20 2018 *)

{a(n) = my(A=[1],L); for(i=0, n, A=concat(A, 0); m=#A; A[m] = Vec( exp(x*(m-1)^2 +x^2*O(x^m)) / Ser(A) )[m] ); L = Vec(Ser(A)'/Ser(A)); L[n+1]}
for(n=0,25, print1( a(n),", "))

Logarithmic derivative of the o.g.f. of A304322.
For n>=1, a(n) = B_{n+1}((n+1)^2-0!*a(0),-1!*a(1),...,-(n-1)!*a(n-1),0) / n!, where B_{n+1}(...) is the (n+1)-st complete exponential Bell polynomial. - Max Alekseyev, Jun 18 2018
a(n) ~ sqrt(1-c) * 2^(2*n + 3/2) * n^(n + 3/2) / (sqrt(Pi) * c^(n+1) * (2-c)^(n+1) * exp(n)), where c = -A226775 = -LambertW(-2*exp(-2)). - Vaclav Kotesovec, Aug 31 2020

A304323 O.g.f. A(x) satisfies: [x^n] exp( n^3 * x ) / A(x) = 0 for n>0.

Original entry on oeis.org

1, 1, 25, 2317, 466241, 162016980, 85975473871, 64545532370208, 65062315637060121, 84756897268784533255, 138581022247955235150982, 277878562828788369685779910, 670574499099019193091230751539, 1917288315895234006935990419270242, 6409780596355519454337664637246378856, 24774712941456386970945752104780461007848, 109632095120643795798521114315908854415860345

Offset: 0

Paul D. Hanna, May 11 2018

nonn

It is conjectured that the coefficients of o.g.f. A(x) consist entirely of integers.
Equals row 3 of table A304320.
O.g.f. A(x) = 1/(1 - x*B(x)), where B(x) is the o.g.f. of A107675.
Logarithmic derivative of o.g.f. A(x), A'(x)/A(x), equals o.g.f. of A304312.
Conjecture: given o.g.f. A(x), the coefficient of x^n in A'(x)/A(x) is the number of connected n-state finite automata with 3 inputs (A006692).

			O.g.f.: A(x) = 1 + x + 25*x^2 + 2317*x^3 + 466241*x^4 + 162016980*x^5 + 85975473871*x^6 + 64545532370208*x^7 + 65062315637060121*x^8 + ...
ILLUSTRATION OF DEFINITION.
The table of coefficients of x^k/k! in exp(n^3*x) / A(x) begins:
n=0: [1, -1, -48, -13608, -11065344, -19317285000, -61649646030720, ...];
n=1: [1, 0, -49, -13754, -11120067, -19372748284, -61765715993765, ...];
n=2: [1, 7, 0, -14440, -11517184, -19768841352, -62587640670464, ...];
n=3: [1, 26, 627, 0, -12292251, -20908064898, -64905483973113, ...];
n=4: [1, 63, 3920, 227032, 0, -22551552136, -69768485886848, ...];
n=5: [1, 124, 15327, 1874642, 213958781, 0, -75806801733845, ...];
n=6: [1, 215, 46176, 9893016, 2100211968, 416846973816, 0, ...];
n=7: [1, 342, 116915, 39937660, 13616254341, 4604681316698, 1458047845980391, 0, ...]; ...
in which the main diagonal is all zeros after the initial term, illustrating that [x^n] exp( n^3*x ) / A(x) = 0 for n>=0.
LOGARITHMIC DERIVATIVE.
The logarithmic derivative of A(x) yields the o.g.f. of A304313:
A'(x)/A(x) = 1 + 49*x + 6877*x^2 + 1854545*x^3 + 807478656*x^4 + 514798204147*x^5 + 451182323794896*x^6 + 519961864703259753*x^7 + ... + A304313(n)*x^n +...
INVERT TRANSFORM.
1/A(x) = 1 - x*B(x), where B(x) is the o.g.f. of A107675:
B(x) = 1 + 24*x + 2268*x^2 + 461056*x^3 + 160977375*x^4 + 85624508376*x^5 + 64363893844726*x^6 + ... + A107675(n)*x^n + ...

Paul D. Hanna, Table of n, a(n) for n = 0..300

Cf. A304320, A304313, A304321, A304322, A304324, A304325.

Cf. A006691, A107675.

{a(n) = my(A=[1]); for(i=1, n, A=concat(A, 0); m=#A; A[m] = Vec( exp(x*(m-1)^3 +x*O(x^m)) / Ser(A) )[m] ); A[n+1]}
for(n=0,25, print1( a(n),", "))

a(n) ~ sqrt(1-c) * 3^(3*n) * n^(2*n - 1/2) / (sqrt(2*Pi) * c^n * (3-c)^(2*n) * exp(2*n)), where c = -A226750 = -LambertW(-3*exp(-3)). - Vaclav Kotesovec, Aug 31 2020

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

Original entry on oeis.org

1, 9, 296, 20958, 2554344, 474099840, 124074010080, 43429847756400, 19565965561887360, 11018376449767451520, 7579467449864423769600, 6251471405353507523097600, 6087988343847192559805952000, 6910412728595671664966422425600, 9042510998634333921282477985689600

Offset: 1

N. J. A. Sloane

nonn

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.

Cf. A006689, A006691, A027835.

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

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

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]

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

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

cp's OEIS Frontend

A304321 Table of coefficients in row functions F'(n,x)/F(n,x) such that [x^k] exp( k^n * x ) / F(n,x) = 0 for k>=1 and n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A304322 O.g.f. A(x) satisfies: [x^n] exp( n^2 * x ) / A(x) = 0 for n>0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A304312 Logarithmic derivative of F(x) that satisfies: [x^n] exp( n^2 * x ) / F(x) = 0 for n>0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A304323 O.g.f. A(x) satisfies: [x^n] exp( n^3 * x ) / A(x) = 0 for n>0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions