A116508 -id:A116508 - cp's OEIS frontend

A367862 Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.

1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

Unlike the connected case (A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.

			Non-isomorphic representatives of the a(4) = 20 graphs:
  {}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,4},{2,3}}
  {{1,2},{1,3},{2,4},{3,4}}

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

The connected case is A057500, unlabeled A001429.
Counting all vertices (not just covered) gives A116508.
The covering case is A367863, unlabeled A006649.
For set-systems we have A367916, ranks A367917.
A001187 counts connected graphs, A001349 unlabeled.
A003465 counts covering set-systems, unlabeled A055621, ranks A326754.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A323818 counts connected set-systems, unlabeled A323819, ranks A326749.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A006126, A316983, A321405, A326754, A326870, A326877, A367770, A367901, A367902, A367903.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[#]==Length[Union@@#]&]],{n,0,5}]

\\ Here b(n) is A367863(n)
b(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n))
a(n) = sum(k=0, n, binomial(n,k) * b(k)) \\ Andrew Howroyd, Dec 29 2023

Binomial transform of A367863.

Terms a(8) and beyond from Andrew Howroyd, Dec 29 2023

A005703 Number of n-node connected graphs with at most one cycle.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 19, 44, 112, 287, 763, 2041, 5577, 15300, 42419, 118122, 330785, 929469, 2621272, 7411706, 21010378, 59682057, 169859257, 484234165, 1382567947, 3952860475, 11315775161, 32430737380, 93044797486, 267211342954, 768096496093, 2209772802169

Offset: 0

N. J. A. Sloane, R. K. Guy

a(n) is the number of pseudotrees on n nodes. - Eric W. Weisstein, Jun 11 2012

Also unlabeled connected graphs covering n vertices with at most n edges. For this definition we have a(1) = 0 and possibly a(0) = 0. - Gus Wiseman, Feb 20 2024

			From _Gus Wiseman_, Feb 20 2024: (Start)
Representatives of the a(0) = 1 through a(5) = 8 graphs:
  {}  .  {12}  {12,13}     {12,13,14}     {12,13,14,15}
               {12,13,23}  {12,13,24}     {12,13,14,25}
                           {12,13,14,23}  {12,13,24,35}
                           {12,13,24,34}  {12,13,14,15,23}
                                          {12,13,14,23,25}
                                          {12,13,14,23,45}
                                          {12,13,14,25,35}
                                          {12,13,24,35,45}
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Washington Bomfim, Table of n, a(n) for n = 0..500
R. K. Guy, Letters to N. J. A. Sloane and J. W. Moon, 1988
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Eric Weisstein's World of Mathematics, Pseudotree
Wikipedia, Pseudoforest

Cf. A000055, A000081, A001429 (labeled A057500), A134964 (number of pseudoforests, labeled A133686).
The labeled version is A129271.
The connected complement is A140636, labeled A140638.
Non-connected: A368834 (labeled A367869) or A370316 (labeled A369191).
A001187 counts connected graphs, unlabeled A001349.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A062734 counts connected graphs by number of edges.
Cf. A000272, A006649, A116508, A140637, A143543, A367862, A367863, A368951, A369197, A370317, A370318.

Needs["Combinatorica`"]; nn = 20; t[x_] := Sum[a[n] x^n, {n, 1, nn}];
a[0] = 0;
b = Drop[Flatten[
    sol = SolveAlways[
      0 == Series[
        t[x] - x Product[1/(1 - x^i)^a[i], {i, 1, nn}], {x, 0, nn}],
      x]; Table[a[n], {n, 0, nn}] /. sol], 1];
r[x_] := Sum[b[[n]] x^n, {n, 1, nn}]; c =
Drop[Table[
    CoefficientList[
     Series[CycleIndex[DihedralGroup[n], s] /.
       Table[s[i] -> r[x^i], {i, 1, n}], {x, 0, nn}], x], {n, 3,
     nn}] // Total, 1];
d[x_] := Sum[c[[n]] x^n, {n, 1, nn}]; CoefficientList[
Series[r[x] - (r[x]^2 - r[x^2])/2 + d[x] + 1, {x, 0, nn}], x] (* Geoffrey Critzer, Nov 17 2014 *)

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec(1 + g(1) + (g(2) - g(1)^2)/2 + sum(k=3, n, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2)}; \\ Andrew Howroyd and Washington Bomfim, May 15 2021

a(n) = A000055(n) + A001429(n).

More terms from Vladeta Jovovic, Apr 19 2000 and from Michael Somos, Apr 26 2000

a(27) corrected and a(28) and a(29) computed by Washington Bomfim, May 14 2008

A140638 Number of connected graphs on n labeled nodes that contain at least two cycles.

Original entry on oeis.org

0, 0, 0, 7, 381, 21748, 1781154, 249849880, 66257728763, 34495508486976, 35641629989151608, 73354595357480683904, 301272202621204113362497, 2471648811029413368450098688, 40527680937730440155535277704046, 1328578958335783199341353852258282496

Offset: 1

Washington Bomfim, May 21 2008

nonn

These are the connected graphs that are neither trees nor unicyclic.

Also connected non-choosable graphs covering n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The unlabeled version is A140636. The complement is counted by A129271. - Gus Wiseman, Feb 20 2024

J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

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

The unlabeled version is A140636.
Cf. A000272 (trees), A001187 (connected graphs), A057500 (connected unicyclic graphs).
The complement is counted by A129271, unlabeled A005703.
The non-connected complement is A133686, covering A367869.
The non-connected version is A367867, unlabeled A140637.
The non-connected covering version is A367868.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A143543 counts simple labeled graphs by number of connected components.
Cf. A001349, A116508, A355740, A367769, A367863, A367901, A367903, A370317.

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}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&Select[Tuples[#],UnsameQ@@#&]=={}&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

seq(n)={my(A=O(x*x^n), t=-lambertw(-x + A)); Vec(serlaplace( log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, A)) - log(1/(1-t))/2 - t/2 + 3*t^2/4), -n)} \\ Andrew Howroyd, Jan 15 2022

a(n) = A001187(n) - A129271(n).

a(n) = A001187(n) - A000272(n) - A057500(n).

Definition clarified by Andrew Howroyd, Jan 15 2022

A137917 a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.

Original entry on oeis.org

1, 0, 0, 1, 2, 5, 14, 35, 97, 264, 733, 2034, 5728, 16101, 45595, 129327, 368093, 1049520, 2999415, 8584857, 24612114, 70652441, 203075740, 584339171, 1683151508, 4852736072, 14003298194, 40441136815, 116880901512, 338040071375, 978314772989, 2833067885748, 8208952443400

Offset: 0

Washington Bomfim, Feb 24 2008

nonn

a(n) is the number of simple unlabeled graphs on n nodes whose components have exactly one cycle. - Geoffrey Critzer, Oct 12 2012

Also the number of unlabeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. - Gus Wiseman, Jan 25 2024

			From _Gus Wiseman_, Jan 25 2024: (Start)
Representatives of the a(0) = 1 through a(5) = 5 simple graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}
                        {12,13,24,34}  {12,13,14,23,25}
                                       {12,13,14,23,45}
                                       {12,13,14,25,35}
                                       {12,13,24,35,45}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..500
F. Ruskey, Combinatorial Generation, p. 79, Eq.(4.27), 2003
Eric Weisstein's World of Mathematics, Pseudoforest.
Wikipedia, Pseudoforest.

Cf. A008483, A137918.
The connected case is A001429.
Without the choice condition we have A001434, covering A006649.
For any number of edges we have A134964, complement A140637.
The labeled version is A137916.
The version with loops is A369145, complement A368835.
The complement is counted by A369201, labeled A369143, covering A369144.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
Cf. A000088, A000612, A007716, A014068, A053530, A116508, A133686, A140638, A368601, A369141, A369146.

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];c=Drop[Apply[Plus,Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,3,nn}]],1];CoefficientList[Series[Product[1/(1-x^i)^c[[i]],{i,1,nn-1}],{x,0,nn}],x]   (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
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/@Select[Subsets[Subsets[Range[n],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]!={}&]]],{n,0,5}] (* Gus Wiseman, Jan 25 2024 *)

a(n) = Sum_{1*j_1 + 2*j_2 + ... = n} (Product_{i=3..n} binomial(A001429(i) + j_i -1, j_i)). [F. Ruskey p. 79, (4.27) with n replaced by n+1, and a_i replaced by A001429(i)].

Euler transform of A001429. - Geoffrey Critzer, Oct 12 2012

Edited by Washington Bomfim, Jun 27 2012
Terms a(30) and beyond from Andrew Howroyd, May 05 2018
Offset changed to 0 by Gus Wiseman, Jan 27 2024

A136556 a(n) = binomial(2^n - 1, n).

Original entry on oeis.org

1, 1, 3, 35, 1365, 169911, 67945521, 89356415775, 396861704798625, 6098989894499557055, 331001552386330913728641, 64483955378425999076128999167, 45677647585984911164223317311276545, 118839819203635450208125966070067352769535, 1144686912178270649701033287538093722740144666625

Offset: 0

Paul D. Hanna, Jan 07 2008; Paul Hanna and Vladeta Jovovic, Jan 15 2008

nonn

Number of n x n binary matrices without zero rows and with distinct rows up to permutation of rows, cf. A014070.
Row 0 of square array A136555.
From Gus Wiseman, Dec 19 2023: (Start)
Also the number of n-element sets of nonempty subsets of {1..n}, or set-systems with n vertices and n edges (not necessarily covering). The covering case is A054780. For example, the a(3) = 35 set-systems are:
  {1}{2}{3}  {1}{2}{12}  {1}{2}{123}  {1}{12}{123}  {12}{13}{123}
             {1}{2}{13}  {1}{3}{123}  {1}{13}{123}  {12}{23}{123}
             {1}{2}{23}  {1}{12}{13}  {1}{23}{123}  {13}{23}{123}
             {1}{3}{12}  {1}{12}{23}  {2}{12}{123}
             {1}{3}{13}  {1}{13}{23}  {2}{13}{123}
             {1}{3}{23}  {2}{3}{123}  {2}{23}{123}
             {2}{3}{12}  {2}{12}{13}  {3}{12}{123}
             {2}{3}{13}  {2}{12}{23}  {3}{13}{123}
             {2}{3}{23}  {2}{13}{23}  {3}{23}{123}
                         {3}{12}{13}  {12}{13}{23}
                         {3}{12}{23}
                         {3}{13}{23}
Of these, only {{1},{2},{1,2}}, {{1},{3},{1,3}}, and {{2},{3},{2,3}} do not cover the vertex set.
(End)

			G.f.: A(x) = 1 + x + 3*x^2 + 35*x^3 + 1365*x^4 + 169911*x^5 +...
A(x) = 1/(1+x) + log(1+2*x)/(1+2*x) + log(1+4*x)^2/(2!*(1+4*x)) + log(1+8*x)^3/(3!*(1+8*x)) + log(1+16*x)^4/(4!*(1+16*x)) + log(1+32*x)^5/(5!*(1+32*x)) +...

G. C. Greubel, Table of n, a(n) for n = 0..50

Sequences of the form binomial(2^n +p*n +q, n): this sequence (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
Cf. A066384, A136555, A136557.
The covering case A054780 has binomial transform A367916, ranks A367917.
Connected graphs of this type are A057500, unlabeled A001429.
Graphs of this type are A116508, covering A367863, unlabeled A006649.
A003465 counts set-systems covering {1..n}, unlabeled A055621.
A058891 counts set-systems, connected A323818, without singletons A016031.
Cf. A055154, A059201, A133686, A367862, A367902, A367903.

[Binomial(2^n -1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021

A136556:= n-> binomial(2^n-1,n); seq(A136556(n), n=0..20); # G. C. Greubel, Mar 14 2021

f[n_] := Binomial[2^n - 1, n]; Array[f, 12] (* Robert G. Wilson v *)
Table[Length[Subsets[Rest[Subsets[Range[n]]],{n}]],{n,0,4}] (* Gus Wiseman, Dec 19 2023 *)

{a(n) = binomial(2^n-1,n)}
for(n=0, 20, print1(a(n), ", "))

/* As coefficient of x^n in the g.f.: */
{a(n) = polcoeff( sum(i=0,n, 1/(1 + 2^i*x +x*O(x^n)) * log(1 + 2^i*x +x*O(x^n))^i/i!), n)}
for(n=0, 20, print1(a(n), ", "))

from math import comb
def A136556(n): return comb((1<Chai Wah Wu, Jan 02 2024

[binomial(2^n -1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(2^n,k).
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k) * (2^n-1)^k.
G.f.: Sum_{n>=0} log(1 + 2^n*x)^n / (n! * (1 + 2^n*x)).
a(n) ~ 2^(n^2)/n!. - Vaclav Kotesovec, Jul 02 2016

Edited by N. J. A. Sloane, Jan 26 2008

A368597 Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges.

Original entry on oeis.org

1, 1, 3, 17, 150, 1803, 27364, 501015, 10736010, 263461265, 7283725704, 223967628066, 7581128184175, 280103206674480, 11216492736563655, 483875783716549277, 22371631078155742764, 1103548801569848115255, 57849356643299101021960, 3211439288584038922502820

Offset: 0

Gus Wiseman, Jan 04 2024

nonn

It doesn't matter for this sequence whether we use loops such as {x,x} or half-loops such as {x}.

			The a(0) = 1 through a(3) = 17 set-systems:
  {}  {{1}}  {{1},{2}}    {{1},{2},{3}}
             {{1},{1,2}}  {{1},{2},{1,3}}
             {{2},{1,2}}  {{1},{2},{2,3}}
                          {{1},{3},{1,2}}
                          {{1},{3},{2,3}}
                          {{2},{3},{1,2}}
                          {{2},{3},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1},{1,3},{2,3}}
                          {{2},{1,2},{1,3}}
                          {{2},{1,2},{2,3}}
                          {{2},{1,3},{2,3}}
                          {{3},{1,2},{1,3}}
                          {{3},{1,2},{2,3}}
                          {{3},{1,3},{2,3}}
                          {{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.

This is the covering case of A014068.
Allowing edges of any positive size gives A054780, covering case of A136556.
Allowing any number of edges gives A322661, connected A062740.
The case of just pairs is A367863, covering case of A116508.
The unlabeled version is A368599.
The version contradicting strict AOC is A368730.
The connected case is A368951.
A000085 counts set partitions into singletons or pairs.
A006129 counts covering graphs, connected A001187.
A058891 counts set-systems, unlabeled A000612.
A100861 counts set partitions into singletons or pairs by number of pairs.
A111924 counts set partitions into singletons or pairs by length.
Cf. A000272, A000666, A057500, A066383, A333331, A367869, A368596, A368600, A368928, A368951, A369199.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}], {n}],Union@@#==Range[n]&]],{n,0,5}]

a(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k+1,2), n)) \\ Andrew Howroyd, Jan 06 2024

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * binomial(binomial(k+1,2), n). - Andrew Howroyd, Jan 06 2024

Terms a(7) and beyond from Andrew Howroyd, Jan 06 2024

A368927 Number of labeled loop-graphs covering a subset of {1..n} such that it is possible to choose a different vertex from each edge.

Original entry on oeis.org

1, 2, 7, 39, 314, 3374, 45630, 744917, 14245978, 312182262, 7708544246, 211688132465, 6397720048692, 210975024924386, 7537162523676076, 289952739051570639, 11949100971787370300, 525142845422124145682, 24515591201199758681892, 1211486045654016217202663

Offset: 0

Gus Wiseman, Jan 15 2024

nonn

These are loop-graphs where every connected component has a number of edges less than or equal to the number of vertices. Also loop-graphs with at most one cycle (unicyclic) in each connected component.

			The a(0) = 1 through a(2) = 7 loop-graphs (loops shown as singletons):
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}

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

Without the choice condition we have A006125.
The case of a unique choice is A088957, unlabeled A087803.
The case without loops is A133686, complement A367867, covering A367869.
For exactly n edges and no loops we have A137916, unlabeled A137917.
For exactly n edges we have A333331 (maybe), complement A368596.
For edges of any positive size we have A367902, complement A367903.
The covering case is A369140, complement A369142.
The complement is counted by A369141.
The complement for n edges and no loops is A369143, covering A369144.
The unlabeled version is A369145, complement A369146.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts labeled covering loop-graphs, connected A062740.
Cf. A000169, A000272, A000666, A014068, A057500, A116508, A367863, A368601, A368924, A368984, A369200.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}]

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(exp(3*t/2 - 3*t^2/4)/sqrt(1-t) ))} \\ Andrew Howroyd, Feb 02 2024

Binomial transform of A369140.
Exponential transform of A369197 with A369197(1) = 2.
E.g.f.: exp(3*T(x)/2 - 3*T(x)^2/4)/sqrt(1-T(x)), where T(x) is the e.g.f. of A000169. - Andrew Howroyd, Feb 02 2024

a(7) onwards from Andrew Howroyd, Feb 02 2024

A369141 Number of labeled loop-graphs covering a subset of {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 25, 710, 29394, 2051522, 267690539, 68705230758, 35184059906570, 36028789310419722, 73786976083150073999, 302231454897259573627852, 2475880078570549574773324062, 40564819207303333310731978895956, 1329227995784915872613854321228773937

Offset: 0

Gus Wiseman, Jan 20 2024

nonn

Also labeled loop-graphs having at least one connected component containing more edges than vertices.

			The a(0) = 0 through a(3) = 25 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{1,2}}
                         {{1},{3},{1,3}}
                         {{2},{3},{2,3}}
                         {{1},{2},{3},{1,2}}
                         {{1},{2},{3},{1,3}}
                         {{1},{2},{3},{2,3}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,2},{2,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3}}
                         {{1},{3},{1,2},{2,3}}
                         {{1},{3},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3}}
                         {{2},{3},{1,2},{2,3}}
                         {{2},{3},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{2},{1,2},{1,3},{2,3}}
                         {{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{3},{1,2},{2,3}}
                         {{1},{2},{3},{1,3},{2,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

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

Without the choice condition we have A006125, unlabeled A000088.
The case of a unique choice is A088957, unlabeled A087803.
The case without loops is A367867, covering A367868.
For edges of any positive size we have A367903, complement A367902.
For exactly n edges we have A368596, complement A333331 (maybe).
The complement is counted by A368927, covering A369140.
The covering case is A369142.
For n edges and no loops we have A369143, covering A369144.
The unlabeled version is A369146 (covering A369147), complement A369145.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable graphs, covering A367869.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
Cf. A000272, A000666, A006649, A062740, A116508, A137916, A368924, A368984, A369194.

Table[Length[Select[Subsets[Subsets[Range[n], {1,2}]],Length[Select[Tuples[#],UnsameQ@@#&]]==0&]],{n,0,5}]

Binomial transform of A369142.

a(n) = A006125(n + 1) - A368927(n). - Andrew Howroyd, Feb 02 2024

a(6) onwards from Andrew Howroyd, Feb 02 2024

A084546 Triangle read by rows: T(n,k) = C( C(n,2), k) for n >= 0, 0 <= k <= C(n,2).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 15, 6, 1, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 1, 21, 210, 1330, 5985, 20349, 54264, 116280, 203490, 293930, 352716, 352716, 293930, 203490, 116280, 54264, 20349, 5985, 1330, 210, 21, 1

Offset: 0

N. J. A. Sloane, Jul 13 2003

T(n,k) gives number of labeled simple graphs with n nodes and k edges.

			Triangle begins:
  1;
  1;
  1, 1;
  1, 3,  3,  1;
  1, 6, 15, 20, 15, 6, 1;
  ...

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 517.

Alois P. Heinz, Rows n = 0..42, flattened
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) table 66.

Cf. A083029. A subset of the rows of Pascal's triangle A007318.
Cf. A006125 (row sums), A008406 (unlabeled graphs).
Main diagonal gives A116508.

C:= binomial:
T:= (n, k)-> C( C(n, 2), k):
seq(seq(T(n, k), k=0..C(n, 2)), n=0..10);  # Alois P. Heinz, Feb 17 2023

Table[Table[Binomial[Binomial[n,2],k],{k,0,Binomial[n,2]}],{n,1,7}]//Grid (* Geoffrey Critzer, Apr 28 2011 *)

T(0,0)=1 prepended by Alois P. Heinz, Feb 17 2023

A369197 Number of labeled connected loop-graphs with n vertices, none isolated, and at most n edges.

Original entry on oeis.org

1, 1, 3, 13, 95, 972, 12732, 202751, 3795864, 81609030, 1980107840, 53497226337, 1592294308992, 51758060711792, 1824081614046720, 69272000503031475, 2819906639193992192, 122488526636380368714, 5654657850859704139776, 276462849597009068108405, 14270030377126199463936000

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

			The a(0) = 0 through a(3) = 13 loop-graphs (loops shown as singletons):
  .  {{1}}  {{1,2}}      {{1,2},{1,3}}
            {{1},{1,2}}  {{1,2},{2,3}}
            {{2},{1,2}}  {{1,3},{2,3}}
                         {{1},{1,2},{1,3}}
                         {{1},{1,2},{2,3}}
                         {{1},{1,3},{2,3}}
                         {{2},{1,2},{1,3}}
                         {{2},{1,2},{2,3}}
                         {{2},{1,3},{2,3}}
                         {{3},{1,2},{1,3}}
                         {{3},{1,2},{2,3}}
                         {{3},{1,3},{2,3}}
                         {{1,2},{1,3},{2,3}}

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

The minimal case is A000272.
Connected case of A066383 and A369196, loopless A369192 and A369193.
The loopless case is A129271, connected case of A369191.
The case of equality is A368951, connected case of A368597.
This is the connected case of A369194.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A001187 counts connected graphs, unlabeled A001349.
A006125 counts (simple) graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A062740 counts connected loop-graphs.
A322661 counts covering loop-graphs, unlabeled A322700.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000169, A000666, A001429, A005703, A006649, A057500, A116508, A140638, A143543, A367863, A369145.

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(log(1/(1-t))/2 + 3*t/2 - 3*t^2/4 + 1 - x))} \\ Andrew Howroyd, Feb 02 2024

Logarithmic transform of A368927.
From Andrew Howroyd, Feb 02 2024: (Start)
a(n) = A000169(n) + A129271(n).
E.g.f.: log(1/(1-T(x)))/2 + 3*T(x)/2 - 3*T(x)^2/4 + 1 - x, where T(x) is the e.g.f. of A000169. (End)

a(0) changed to 1 and a(7) onwards from Andrew Howroyd, Feb 02 2024

cp's OEIS Frontend

A367862 Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A005703 Number of n-node connected graphs with at most one cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A140638 Number of connected graphs on n labeled nodes that contain at least two cycles.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A137917 a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A136556 a(n) = binomial(2^n - 1, n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A368597 Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs