A057500 -id:A057500 - cp's OEIS frontend

A061540 Number of connected labeled graphs with n nodes and n+1 edges.

0, 0, 0, 6, 205, 5700, 156555, 4483360, 136368414, 4432075200, 154060613850, 5720327205120, 226378594906035, 9523895202838016, 424814409531910125, 20037831121798963200, 996964614369038858060, 52198565072252054814720, 2869621989939313379211204, 165302832533722012508160000

Offset: 1

RAVELOMANANA Vlady (vlad(AT)lri.fr), May 16 2001

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 407, Eq. (6.5).

Sergey Serebryakov, Table of n, a(n) for n = 1..40
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
E. M. Wright, The Number of Connected Sparsely Edged Graphs, Journal of Graph Theory Vol. 1 (1977), 317-330.

A diagonal of A343088.

Cf. A000169, A000272, A057500, A061541, A061542, A061543, A096117, A061544, A096150, A096224.

A001864 := proc(n)
    add(binomial(n,s)*s^s*(n-s)^(n-s),s=1..n-1) ;
end proc:
A061540 := proc(n)
    (n-1)*(5*n^2+3*n+2)*n^(n-2)-14*A001864(n) ;
    %/24 ;
end proc: # R. J. Mathar, May 10 2016 see Chapter 6.3 in Bona's Handbook of Combinatorics

max = 18; t[x_] := -ProductLog[-x]; w1[x_] := t[x]^4/24*(6-t[x])/(1-t[x])^3; Drop[ CoefficientList[ Series[ w1[x], {x, 0, max}], x]*Range[0, max]!, 1] (* Jean-François Alcover, Apr 02 2012, after e.g.f. *)

from math import comb
def A061540(n): return 0 if n<2 else ((n*(n*(5*n - 2) - 1) - 2)*n**(n-2)-14*((sum(comb(n,k)*(n-k)**(n-k)*k**k for k in range(1,(n+1>>1)))<<1) + (0 if n&1 else comb(n,m:=n>>1)*m**n)))//24 # Chai Wah Wu, Apr 26 2023

E.g.f.: W1(x) := T(x)^4/24 * (6-T(x))/(1-T(x))^3 where T(x) is the e.g.f. for rooted labeled trees (A000169), i.e. T(x) = -LambertW(-x) = x*exp(T(x)).

a(n) ~ 5*n^(n+1)/24 * (1 - 7/5*sqrt(2*Pi/n)). - Vaclav Kotesovec, Jul 09 2013

A144228 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph has at most one cycle.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 3, 1, 1, 6, 15, 20, 15, 1, 10, 45, 120, 210, 222, 1, 15, 105, 455, 1365, 2913, 3670, 1, 21, 210, 1330, 5985, 20139, 49294, 68820, 1, 28, 378, 3276, 20475, 97860, 362670, 976560, 1456875, 1, 36, 630, 7140, 58905, 376236, 1914276, 7663500, 22089870, 34506640

Offset: 0

Alois P. Heinz, Sep 15 2008

			T(4,4) = 15, because there are 15 simple graphs on 4 labeled nodes with 4 edges where each maximally connected subgraph has at most one cycle:
  1-2  1-2  1-2  1-2  1-2  1-2  1 2  1 2  1-2  1 2  1 2  1-2  1-2  1-2  1 2
  |/|  |X   |/   |\|   X|   \|  |/|   X|   /|  |\|  |X   |\   | |   X   |X|
  4 3  4 3  4-3  4 3  4 3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4 3
Triangle begins:
  1;
  1,  0;
  1,  1,  0;
  1,  3,  3,   1;
  1,  6, 15,  20,  15;
  1, 10, 45, 120, 210, 222;
  ...

Alois P. Heinz, Table of n, a(n) for n = 0..140, flattened

Columns k=0-3 give: A000012, A000217, A050534, A093566.
Main diagonal gives A137916.
Row sums give: A133686.
T(2n,n) gives A369828.
Cf. A000272, A057500, A007318, A000142, A129271.

cy:= proc(n) option remember; local t; binomial(n-1, 2) *add((n-3)! /(n-2-t)! *n^(n-2-t), t=1..n-2) end: T:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n

t[, 0] = 1; t[n, k_] /; (k<0 || nJean-François Alcover, Jan 15 2014, after Maple *)

T(n,0) = 1, T(n,k) = 0 if k<0 or nA000272(j+1) T(n-j-1,k-j) + A057500(j+1) T(n-j-1,k-j-1)).

E.g.f.: exp(B(x,y)), where B(x,y) = Sum(Sum(A062734(n,k)*y^k*x^n/n!, k=0..n), n=1..infinity) = -1/2*log(1+LambertW(-x*y))+1/2*LambertW(-x*y) -1/4*LambertW(-x*y)^2-1/y *(LambertW(-x*y)+1/2 *LambertW(-x*y)^2). - Vladeta Jovovic, Sep 16 2008

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 10, 97, 2160, 126862, 21485262, 11105374322, 18109358131513, 95465831661532570, 1660400673336788987026, 96929369602251313489896310, 19268528295096123543660356281600, 13203875101002459910158494602665950757, 31517691852305548841992346407978317698725021

Offset: 0

Gus Wiseman, Jan 07 2024

nonn

			Non-isomorphic representatives of the a(3) = 10 set-systems:
  {{1},{2},{3}}
  {{1},{2},{1,2}}
  {{1},{2},{1,3}}
  {{1},{2},{1,2,3}}
  {{1},{1,2},{1,3}}
  {{1},{1,2},{2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The case of graphs is A001434, labeled A116508.
Labeled version is A136556, covering A054780, binomial transform of A367916.
The case of labeled covering graphs is A367863, binomial transform A367862.
These include the set-systems ranked by A367917.
The covering case is A368186, for graphs A006649, connected A057500.
Requiring all edges to be singletons or pairs gives A368598.
A003465 counts covers with any number of edges, unlabeled A055621.
A046165 counts minimal covers, ranks A309326.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
Cf. A000088, A007716, A283877, A367901, A367902, A367903, A368599.

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Subsets[Subsets[Range[n],{1,n}],{n}]]],{n,0,4}]

a(n) = polcoef(G(n, n), n) \\ G defined in A368186. - Andrew Howroyd, Jan 11 2024

Terms a(6) and beyond from Andrew Howroyd, Jan 11 2024

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Original entry on oeis.org

0, 0, 0, 1, 19, 307, 5237, 99137, 2098946, 49504458, 1291570014, 37002273654, 1156078150969, 39147186978685, 1428799530304243, 55933568895261791, 2338378885159906196, 103995520598384132516, 4903038902046860966220, 244294315694676224001852, 12827355456239840407125363

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

The case of an empty edge set is excluded.

Andrew Howroyd, Table of n, a(n) for n = 0..100

The covering case is A057500, which is also the covering case of A370317.
This is the connected case of A367862, covering A367863.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by edge count.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A001429, A006649, A061540, A116508, A323818, A367916, A368951, A369197.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[#]==Length[Union@@#] && Length[csm[#]]==1&]],{n,0,5}]

\\ Compare A370317; use A057500 for efficiency.
a(n)=n!*polcoef(polcoef(exp(x*y + O(x*x^n))*(-x+log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*x^k/k!, O(x*x^n)))), n), n) \\ Andrew Howroyd, Feb 19 2024

Binomial transform of A057500 (if the null graph is not connected).

a(n) = n!*[x^n][y^n] exp(x*y)*(-x + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Feb 19 2024

A061541 Number of connected labeled graphs with n nodes and n+2 edges.

Original entry on oeis.org

0, 0, 0, 1, 120, 6165, 258125, 10230360, 405918324, 16530124800, 699126562530, 30884683104000, 1428626760992860, 69248819808744576, 3516693960681822375, 186964957159176734720, 10395215954531344335000, 603712553730550509035520, 36575888366817680447745924

Offset: 1

RAVELOMANANA Vlady (vlad(AT)lri.fr), May 16 2001

Vaclav Kotesovec, Table of n, a(n) for n = 1..380 (first 100 terms from T. D. Noe)
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
S. Janson, D. E. Knuth, T. Łuczak, and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
S. Janson, D. E. Knuth, T. Łuczak, and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
E. M. Wright, The Number of Connected Sparsely Edged Graphs, Journal of Graph Theory Vol. 1 (1977), 317-330.

A diagonal of A343088.

Cf. A000169, A000272, A057500, A061541, A061542, etc.

f[x_] = (1/(48*(1 + ProductLog[-x])^6))* ProductLog[-x]^4*(2 - 28*ProductLog[-x] - 23*ProductLog[-x]^2 - 9*ProductLog[-x]^3 - ProductLog[-x]^4); Rest[CoefficientList[Series[f[x], {x, 0, 17}], x]*Range[0, 17]!] (* Jean-François Alcover, Jul 11 2011, after formula *)

N=66; x='x+O('x^N); /* that many terms */
T=sum(n=1,N,n^(n-1)/n!*x^n); /* e.g.f. of A000169 */
egf=1/48*T^4*(2+28*T-23*T^2+9*T^3-T^4)/(1-T)^6;
Vec(serlaplace(egf)) /* show terms, starting with 1 */
/* Joerg Arndt, Jul 11 2011 */

E.g.f.: W2(x) = (1/48)*T(x)^4*(2 + 28*T(x) - 23*T(x)^2 + 9*T(x)^3 - T(x)^4)/(1 - T(x))^6, where T(x) is the e.g.f. for rooted labeled trees (A000169), i.e., T(x) = -LambertW(-x) = x*exp(T(x)).

a(n) ~ 5*n^(n+5/2)*sqrt(2*Pi)/256 * (1 - 56*sqrt(2)/(9*sqrt(Pi*n))). - Vaclav Kotesovec, Apr 06 2014

A061544 Number of connected labeled graphs with n nodes and n+6 edges.

Original entry on oeis.org

0, 0, 0, 0, 0, 455, 202755, 39183840, 5228627544, 573177986865, 56169415897650, 5157436533796140, 456501786661617840, 39667302684866008152, 3425100498297691978050, 296331952661358892037760, 25839208713048103250144280, 2280203173608621371757204480, 204244225852123476144894896712

Offset: 1

Ravelomanana Vlady (vlad(AT)lri.fr), May 16 2001

G. C. Greubel, Table of n, a(n) for n = 1..380
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
E. M. Wright, The Number of Connected Sparsely Edged Graphs, Journal of Graph Theory Vol. 1 (1977), 317-330.

A diagonal of A343088.

Cf. A000169, A000272, A057500.

t[x_] := -ProductLog[-x]; W6[x_] := -1/5806080*t[x]^6*(-3669120 - 145514880*t[x] - 826813440*t[x]^2 - 160242624*t[x]^3 + 549065304*t[x]^4 - 1423242144*t[x]^5 + 1649073392*t[x]^6 - 1408032768*t[x]^7 + 881917344*t[x]^8 - 418233349*t[x]^9 + 147585749*t[x]^10 - 37755372*t[x]^11 + 6581528*t[x]^12 - 696620*t[x]^13 +33000*t[x]^14)/((-1 + t[x])^18); max = 20; CoefficientList[Series[W6[x], {x, 0, max}], x]*Range[0, max]! // Rest (* G. C. Greubel, Nov 12 2017 *)

E.g.f.: W6(x) = - 1/5806080*T(x)^6*( - 3669120 - 145514880*T(x) - 826813440*T(x)^2 - 160242624*T(x)^3 + 549065304*T(x)^4 - 1423242144*T(x)^5 + 1649073392*T(x)^6 - 1408032768*T(x)^7 + 881917344*T(x)^8 - 418233349*T(x)^9 + 147585749*T(x)^10 - 37755372*T(x)^11 + 6581528*T(x)^12 - 696620*T(x)^13 + 33000*T(x)^14)/(( - 1 + T(x))^18) where T(x) is the e.g.f. for rooted labeled trees (A000169), i.e., T(x) = -LambertW(-x) = x*exp(T(x)).

A096117 Number of connected labeled graphs with n nodes and n+5 edges.

Original entry on oeis.org

0, 0, 0, 0, 1, 1365, 290745, 35804384, 3431889000, 288982989000, 22716104811840, 1724903317684800, 129165517275377154, 9664573656742964960, 728813888470620552600, 55713446610261097382400, 4334305420045397178746260, 344080024970397555374419968, 27923503603736889921687649020

Offset: 1

Keith Briggs, Aug 09 2004

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
S. R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.

A diagonal of A343088.

Cf. A057500.

Offset corrected and terms a(17) and beyond from Andrew Howroyd, Apr 16 2021

A096150 Number of connected labeled graphs with n nodes and n+7 edges.

Original entry on oeis.org

0, 0, 0, 0, 0, 105, 116175, 37007656, 7032842901, 1016662746825, 125217059384890, 13979620699390500, 1468384747758433362, 148610523724144786304, 14725179052834536611325, 1444367897584925254381440, 141356080305700826710780155, 13881663444819892480039097856

Offset: 1

Keith Briggs, Aug 09 2004

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
S. R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.

A diagonal of A343088.

Cf. A057500.

Offset corrected and terms a(16) and beyond from Andrew Howroyd, Apr 16 2021

A096224 Number of connected labeled graphs with n nodes and n+8 edges.

Original entry on oeis.org

0, 0, 0, 0, 0, 15, 54257, 30258935, 8403710364, 1624745199910, 253717024819170, 34644709397517912, 4336461198140896396, 512755474242717445740, 58441126001104710458595, 6511044113057606391228960, 716247426054164600104429648, 78368395883181612191026677504

Offset: 1

Keith Briggs, Aug 09 2004

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
S. R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.

A diagonal of A343088.

Cf. A057500.

Offset corrected and terms a(16) and beyond from Andrew Howroyd, Apr 16 2021

A096542 Triangle, read by rows, where e.g.f. A(x,y) satisfies: A(x,y) = exp(xyA(x,y+1)) and A(x,y) = Sum_{n>=0} Sum_{k>=0} T(n,k)/n!x^ny^k.

Original entry on oeis.org

1, 0, 1, 0, 2, 3, 0, 15, 30, 16, 0, 244, 564, 444, 125, 0, 6885, 17540, 16680, 7320, 1296, 0, 298326, 817470, 877740, 478380, 136590, 16807, 0, 18377191, 53352138, 62582100, 39142600, 14146440, 2873136, 262144, 0, 1525885992, 4645224472

Offset: 0

Paul D. Hanna, Jun 25 2004

Row sums form A096537.
Main diagonal forms A000272 (labeled trees on n nodes).
Secondary diagonal forms 2*A057500 (labeled connected graphs with n edges and n nodes).
Other diagonals include 3*A096543 and 4*A096544.

			A(x,y) = exp(x*y*exp(x*(y+1)*exp(x*(y+2)*exp(...exp(x*(n+y)*exp(...))...)))).
Triangle begins:
1;
0, 1;
0, 2, 3;
0, 15, 30, 16;
0, 244, 564, 444, 125;
0, 6885, 17540, 16680, 7320, 1296;
0, 298326, 817470, 877740, 478380, 136590, 16807;
0, 18377191, 53352138, 62582100, 39142600, 14146440, 2873136, 262144;
0, 1525885992, 4645224472, 5837707848, 4032207480, 1692155640, 441093240, 67558680, 4782969; ...

Paul D. Hanna, Rows n = 0..32, flattened.

Cf. A096537, A000272, A057500, A096543, A096544.

{T(n,k)=local(A=exp(x));for(i=1,n,A=exp(x*(n-i+y)*A+x*O(x^n)+y*O(y^k))); n!*polcoeff(polcoeff(A,k,y),n,x)}

E.g.f. satisfies: A(x, y+1) = log(A(x, y))/(x*y).
T(n, 1) = n*A096537(n).
T(n, n) = (n+1)^(n-1) = A000272(n+1).
T(n, n-1) = 2*A057500(n).

cp's OEIS Frontend

A061540 Number of connected labeled graphs with n nodes and n+1 edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A144228 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph has at most one cycle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A061541 Number of connected labeled graphs with n nodes and n+2 edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A061544 Number of connected labeled graphs with n nodes and n+6 edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A096117 Number of connected labeled graphs with n nodes and n+5 edges.

Views

Author

Keywords

Links

Crossrefs

Extensions

A096150 Number of connected labeled graphs with n nodes and n+7 edges.

Views

Author

Keywords

Links

Crossrefs

Extensions

A096224 Number of connected labeled graphs with n nodes and n+8 edges.

A096542 Triangle, read by rows, where e.g.f. A(x,y) satisfies: A(x,y) = exp(xyA(x,y+1)) and A(x,y) = Sum_{n>=0} Sum_{k>=0} T(n,k)/n!x^ny^k.