A369193 -id:A369193 - cp's OEIS frontend

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

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

A066383 a(n) = Sum_{k=0..n} C(n*(n+1)/2,k).

Original entry on oeis.org

1, 2, 7, 42, 386, 4944, 82160, 1683218, 40999516, 1156626990, 37060382822, 1328700402564, 52676695500313, 2287415069586304, 107943308165833912, 5499354613856855290, 300788453960472434648, 17577197510240126035698, 1092833166733915284972350

Offset: 0

N. J. A. Sloane, Dec 23 2001

nonn

Number of labeled loop-graphs with n vertices and at most n edges. - Gus Wiseman, Feb 14 2024

			From _Gus Wiseman_, Feb 14 2024: (Start)
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}}
(End)

Harry J. Smith, Table of n, a(n) for n = 0..100

The case of equality is A014068, covering A368597.
The loopless version is A369192, covering A369191.
The covering case is A369194, minimal case A001862.
Counting only covered vertices gives A369196, without loops A369193.
The connected covering case is A369197, without loops A129271.
The unlabeled version is A370168, covering A370169.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000085, A000666, A005703, A062740, A116508, A367862, A367863, A367916, A368927, A369141, A369199.

f[n_] := Sum[Binomial[n (n + 1)/2, k], {k, 0, n}]; Array[f, 21, 0] (* Vincenzo Librandi, May 06 2016 *)
Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]],Length[#]<=n&]],{n,0,5}] (* Gus Wiseman, Feb 14 2024 *)

{ for (n=0, 100, a=0; for (k=0, n, a+=binomial(n*(n + 1)/2, k)); write("b066383.txt", n, " ", a) ) } \\ Harry J. Smith, Feb 12 2010

from math import comb
def A066383(n): return sum(comb(comb(n+1,2),k) for k in range(n+1)) # Chai Wah Wu, Jul 10 2024

a(n) = 2^(n*(n+1)/2) - binomial(n*(n+1)/2,n+1)*2F1(1,(-n^2+n+2)/2;n+2;-1) = A006125(n) - A116508(n+1) * 2F1(1,(-n^2+n+2)2;n+2;-1), where 2F1(a,b;c;x) is the hypergeometric function. - Ilya Gutkovskiy, May 06 2016

a(n) ~ exp(n) * n^(n - 1/2) / (sqrt(Pi) * 2^(n + 1/2)). - Vaclav Kotesovec, Feb 20 2024

A369194 Number of labeled loop-graphs covering n vertices with at most n edges.

Original entry on oeis.org

1, 1, 4, 23, 199, 2313, 34015, 606407, 12712643, 306407645, 8346154699, 253476928293, 8490863621050, 310937199521774, 12356288017546937, 529516578044589407, 24339848939829286381, 1194495870124420574751, 62332449791125883072149, 3446265450868329833016605

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

Row-sums of left portion of A369199.

			The a(0) = 1 through a(3) = 23 loop-graphs (loops shown as singletons):
  {}  {{1}}  {{1,2}}      {{1},{2,3}}
             {{1},{2}}    {{2},{1,3}}
             {{1},{1,2}}  {{3},{1,2}}
             {{2},{1,2}}  {{1,2},{1,3}}
                          {{1,2},{2,3}}
                          {{1},{2},{3}}
                          {{1,3},{2,3}}
                          {{1},{2},{1,3}}
                          {{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}}

The minimal case is A001862, without loops A053530.
This is the covering case of A066383 and A369196, cf. A369192 and A369193.
The case of equality is A368597, without loops A367863.
The version without loops is A369191.
The connected case is A369197, without loops A129271.
The unlabeled version is A370169, equality A368599, non-covering A368598.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts simple graphs; also loop-graphs if shifted left.
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 covering loop-graphs, unlabeled A322700.
A367867 counts non-choosable graphs, covering A367868.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000169, A000272, A000666, A003465, A005703, A006649, A057500, A062740, A116508, A367862, A367916.

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

Inverse binomial transform of A369196.

A369191 Number of labeled simple graphs covering n vertices with at most n edges.

Original entry on oeis.org

1, 0, 1, 4, 34, 387, 5686, 102084, 2162168, 52693975, 1450876804, 44509105965, 1504709144203, 55563209785167, 2224667253972242, 95984473918245388, 4439157388017620554, 219067678811211857307, 11489425098298623161164, 638159082104453330569185

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

Row-sums of left portion of A054548.

			The a(0) = 1 through a(3) = 4 graphs:
  {}  .  {{1,2}}  {{1,2},{1,3}}
                  {{1,2},{2,3}}
                  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}

The minimal case is A053530.
The connected case is A129271, unlabeled version A005703.
The case of equality is A367863, covering case of A367862.
This is the covering case of A369192, or A369193 for covered vertices.
The version for loop-graphs is A369194.
The unlabeled version is A370316.
A001187 counts connected graphs, unlabeled A001349.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A057500 counts connected graphs with n vertices and n edges.
A133686 counts choosable graphs, covering A367869.
A367867 counts non-choosable graphs, covering A367868.
Cf. A000169, A000272, A000666, A001429, A003465, A006649, A143543, A116508, A140638, A322661.

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

Inverse binomial transform of A369193.

A369192 Number of labeled simple graphs with n vertices and at most n edges (not necessarily covering).

Original entry on oeis.org

1, 1, 2, 8, 57, 638, 9949, 198440, 4791323, 135142796, 4346814276, 156713948672, 6251579884084, 273172369790743, 12969420360339724, 664551587744173992, 36543412829258260135, 2146170890448154922648, 134053014635659737513358, 8872652968135849629240560

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

			The a(0) = 1 through a(3) = 8 graphs:
  {}  {}  {}       {}
          {{1,2}}  {{1,2}}
                   {{1,3}}
                   {{2,3}}
                   {{1,2},{1,3}}
                   {{1,2},{2,3}}
                   {{1,3},{2,3}}
                   {{1,2},{1,3},{2,3}}

The version for loop-graphs is A066383, covering A369194.
The case of equality is A116508, covering A367863, also A367862.
The connected case is A129271, unlabeled A005703.
The covering case is A369191, minimal case A053530.
Counting only covered vertices gives A369193.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable graphs, covering A367869.
A367867 counts non-choosable graphs, covering A367868.
Cf. A000169, A000272, A000666, A001187, A006649, A057500, A143543.

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

from math import comb
def A369192(n): return sum(comb(comb(n,2),k) for k in range(n+1)) # Chai Wah Wu, Jul 14 2024

a(n) = Sum_{k=0..n} binomial(binomial(n,2),k).

A369196 Number of labeled loop-graphs with n vertices and at most as many edges as covered vertices.

Original entry on oeis.org

1, 2, 7, 39, 320, 3584, 51405, 900947, 18661186, 445827942, 12062839691, 364451604095, 12157649050827, 443713171974080, 17583351295466338, 751745326170662049, 34485624653535808340, 1689485711682987916502, 88030098291829749593643, 4860631073631586486397141

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

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

The version counting all vertices is A066383, without loops A369192.
The loopless case is A369193, with case of equality A367862.
The covering case is A369194, connected A369197, minimal case A001862.
The case of equality is A369198, covering case A368597.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts simple graphs, also loop-graphs if shifted left.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A322661 counts covering loop-graphs, unlabeled A322700.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000169, A000272, A000666, A001187, A006649, A057500, A062740, A116508, A367863, A369145.

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

Binomial transform of A369194.

A370317 Number of labeled graphs with n vertices (allowing isolated vertices) and n edges, such that the edge set is connected.

Original entry on oeis.org

1, 0, 0, 1, 15, 252, 4905, 110715, 2864148, 83838720, 2744568522, 99463408335, 3955626143040, 171344363805582, 8031863998136355, 405150528051451000, 21884686370917378050, 1260420510502767861840, 77105349570138633021624, 4993117552678619556356085

Offset: 0

Gus Wiseman, Feb 17 2024

nonn

			The a(0) = 0 through a(4) = 15 graphs:
  {}  .  .  {{1,2},{1,3},{2,3}}  {{1,2},{1,3},{1,4},{2,3}}
                                 {{1,2},{1,3},{1,4},{2,4}}
                                 {{1,2},{1,3},{1,4},{3,4}}
                                 {{1,2},{1,3},{2,3},{2,4}}
                                 {{1,2},{1,3},{2,3},{3,4}}
                                 {{1,2},{1,3},{2,4},{3,4}}
                                 {{1,2},{1,4},{2,3},{2,4}}
                                 {{1,2},{1,4},{2,3},{3,4}}
                                 {{1,2},{1,4},{2,4},{3,4}}
                                 {{1,2},{2,3},{2,4},{3,4}}
                                 {{1,3},{1,4},{2,3},{2,4}}
                                 {{1,3},{1,4},{2,3},{3,4}}
                                 {{1,3},{1,4},{2,4},{3,4}}
                                 {{1,3},{2,3},{2,4},{3,4}}
                                 {{1,4},{2,3},{2,4},{3,4}}

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

The covering case is A057500.
This is the connected case of A116508.
Allowing any number of edges gives A287689.
Counting only covered vertices gives A370318.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, connected A001187.
A369192 counts graphs with at most n edges, covering A369191.
Cf. A000169, A001862, A054780, A062740, A129271, A367863, A369193, 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[#]==n&&Length[csm[#]]<=1&]], {n,0,5}]

a(n)=n!*polcoef(polcoef(exp(x + O(x*x^n))*(1 + 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

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

a(8) onwards from Andrew Howroyd, Feb 19 2024

A370316 Number of unlabeled simple graphs covering n vertices with at most n edges.

Original entry on oeis.org

1, 0, 1, 2, 5, 10, 28, 68, 193, 534, 1568, 4635, 14146, 43610, 137015, 435227, 1400058, 4547768, 14917504, 49348612, 164596939, 553177992, 1872805144, 6385039022, 21917878860, 75739158828, 263438869515, 922219844982, 3249042441125, 11519128834499, 41097058489426

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

			The a(0) = 1 through a(5) = 10 simple graphs:
  {}  .  {12}  {12-13}     {12-34}        {12-13-45}
               {12-13-23}  {12-13-14}     {12-13-14-15}
                           {12-13-24}     {12-13-14-25}
                           {12-13-14-23}  {12-13-23-45}
                           {12-13-24-34}  {12-13-24-35}
                                          {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}

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

The connected case is A005703, labeled A129271.
The case of exactly n edges is A006649, covering case of A001434.
The labeled version is A369191.
Partial row sums of A370167, covering case of A008406.
The non-covering version with loops is A370168, labeled A066383.
The version with loops is A370169, labeled A369194.
The non-covering version is A370315, labeled A369192.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A054548, A062734, A116508, A367862, A367863, A368599, A369193.

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}],{0,n}], Union@@#==Range[n]&]]],{n,0,5}]

\\ G defined in A008406.
a(n)=my(A=O(x*x^n)); if(n==0, 1, polcoef((G(n,A)-G(n-1,A))/(1-x), n)) \\ Andrew Howroyd, Feb 19 2024

a(8) onwards from Andrew Howroyd, Feb 19 2024

A369198 Number of labeled loop-graphs with n vertices and the same number of edges as covered vertices.

Original entry on oeis.org

1, 2, 6, 30, 241, 2759, 40824, 736342, 15622835, 380668095, 10467815086, 320529284621, 10813165015074, 398413594789777, 15917197015926392, 685312404706694574, 31631317971844128229, 1558017329350990780607, 81567807853701988869120, 4522975947689168088308305

Offset: 0

Gus Wiseman, Jan 18 2024

nonn

			The a(0) = 1 through a(3) = 30 loop-graphs (loops shown as singletons):
  {}  {}     {}           {}
      {{1}}  {{1}}        {{1}}
             {{2}}        {{2}}
             {{1},{2}}    {{3}}
             {{1},{1,2}}  {{1},{2}}
             {{2},{1,2}}  {{1},{3}}
                          {{2},{3}}
                          {{1},{1,2}}
                          {{1},{1,3}}
                          {{2},{1,2}}
                          {{2},{2,3}}
                          {{3},{1,3}}
                          {{3},{2,3}}
                          {{1},{2},{3}}
                          {{1},{2},{1,3}}
                          {{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}}

The version counting all vertices is A014068.
The loopless case is A367862, counting all vertices A116508.
The covering case is A368597, connected A368951.
With inequality we have A369196, covering A369194, connected A369197.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts simple graphs, also loop-graphs if shifted left.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A322661 counts covering loop-graphs, unlabeled A322700.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000272, A000666, A006649, A062740, A066383, A367863, A369192, A369193.

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

Binomial transform of A368597.

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A066383 a(n) = Sum_{k=0..n} C(n*(n+1)/2,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A369194 Number of labeled loop-graphs covering n vertices with at most n edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A369191 Number of labeled simple graphs covering n vertices with at most n edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A369192 Number of labeled simple graphs with n vertices and at most n edges (not necessarily covering).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A369196 Number of labeled loop-graphs with n vertices and at most as many edges as covered vertices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A370317 Number of labeled graphs with n vertices (allowing isolated vertices) and n edges, such that the edge set is connected.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A370316 Number of unlabeled simple graphs covering n vertices with at most n edges.

Views

Author

Keywords