A053530 -id:A053530 - cp's OEIS frontend

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

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.

A372167 Irregular triangle read by rows where T(n,k) is the number of simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Original entry on oeis.org

1, 0, 1, 3, 1, 22, 12, 6, 0, 1, 237, 220, 165, 70, 35, 30, 0, 10, 0, 0, 1, 3961, 5460, 5830, 4140, 2805, 2112, 1230, 720, 600, 180, 230, 60, 45, 60, 0, 0, 15, 0, 0, 0, 1, 99900, 191975, 269220, 272055, 240485, 207095, 166005, 121530, 98770, 65905, 48503, 37065, 20055, 17570, 11445, 6552, 4410, 3570, 1680, 1785, 147, 735, 455, 140, 0, 105, 105, 0, 0, 0, 21, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 23 2024

			Triangle begins:
    1
    0
    1
    3    1
   22   12    6    0    1
  237  220  165   70   35   30    0   10    0    0    1
  ...
Row k = 4 counts the following graphs:
  12-34      12-13-14-23  12-13-14-23-24  .  12-13-14-23-24-34
  13-24      12-13-14-24  12-13-14-23-34
  14-23      12-13-14-34  12-13-14-24-34
  12-13-14   12-13-23-24  12-13-23-24-34
  12-13-24   12-13-23-34  12-14-23-24-34
  12-13-34   12-14-23-24  13-14-23-24-34
  12-14-23   12-14-24-34
  12-14-34   12-23-24-34
  12-23-24   13-14-23-34
  12-23-34   13-14-24-34
  12-24-34   13-23-24-34
  13-14-23   14-23-24-34
  13-14-24
  13-23-24
  13-23-34
  13-24-34
  14-23-24
  14-23-34
  14-24-34
  12-13-24-34
  12-14-23-34
  13-14-23-24

Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)
Gus Wiseman, All simple graphs covering {1,2,3,4} grouped by number of triangles.

Row sums are A006129, unlabeled A002494.
Row lengths are A050407.
Counting edges instead of triangles gives A054548, unlabeled A370167.
Column k = 0 is A372168 (non-covering A213434), unlabeled A372169.
Covering case of A372170, unlabeled A263340.
Column k = 1 is A372171 (non-covering A372172), unlabeled A372174.
The unlabeled version is A372173.
For all cycles (not just triangles) we have A372175, non-covering A372176.
A001858 counts acyclic graphs, unlabeled A005195.
A006125 counts simple graphs, unlabeled A000088.
A105784 counts acyclic covering graphs, unlabeled A144958.
Cf. A000272, A053530, A121251, A137916, A367868, A369199, A372191.

cys[y_]:=Select[Subsets[Union@@y,{3}], MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[cys[#]]==k&]], {n,0,5},{k,0,Binomial[n,3]}]

Inverse binomial transform of columns of A372170.

a(42) onwards from Andrew Howroyd, Dec 29 2024

A372171 Number of labeled simple graphs covering n vertices with a unique triangle.

Original entry on oeis.org

0, 0, 0, 1, 12, 220, 5460, 191975, 9596160, 683389812, 69270116040

Offset: 0

Gus Wiseman, Apr 24 2024

The unlabeled version is A372174.

			The a(4) = 12 graphs:
  12,13,14,23
  12,13,14,24
  12,13,14,34
  12,13,23,24
  12,13,23,34
  12,14,23,24
  12,14,24,34
  12,23,24,34
  13,14,23,34
  13,14,24,34
  13,23,24,34
  14,23,24,34

Column k = 1 of A372167, unlabeled A372173.
For no triangles we have A372168 (non-covering A213434), unlabeled A372169.
The non-covering case is A372172, unlabeled A372194.
The unlabeled version is A372174.
For all cycles (not just triangles) we have A372195, non-covering A372193.
A001858 counts acyclic graphs, unlabeled A005195.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494
A054548 counts labeled covering graphs by edges, unlabeled A370167.
A105784 counts acyclic covering graphs, unlabeled A144958.
A372170 counts graphs by triangles, unlabeled A263340.
A372175 counts covering graphs by cycles, non-covering A372176.
Cf. A000272, A053530, A121251, A137916, A367868, A369199, A372191.

cys[y_]:=Select[Subsets[Union@@y,{3}],MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Union@@#==Range[n]&&Length[cys[#]]==1&]],{n,0,5}]

Inverse binomial transform of A372172.

a(7)-a(10) from Andrew Howroyd, Aug 01 2024

A372173 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Original entry on oeis.org

1, 0, 1, 1, 1, 4, 1, 1, 0, 1, 7, 5, 4, 2, 2, 1, 0, 1, 0, 0, 1, 24, 16, 23, 12, 15, 8, 7, 4, 4, 1, 3, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 69, 79, 113, 103, 105, 83, 73, 58, 45, 34, 31, 22, 14, 16, 10, 4, 8, 5, 2, 3, 2, 2, 2, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 23 2024

			Triangle begins:
  1
  0
  1
  1 1
  4 1 1 0 1
  7 5 4 2 2 1 0 1 0 0 1

Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)
Gus Wiseman, All unlabeled simple graphs covering 5 vertices, grouped by number of triangles.

Row sums are A002494, labeled A006129.
Row lengths are A050407.
The non-covering version is A263340, labeled A372170.
Counting edges instead of triangles gives A370167, labeled A054548.
The labeled version is A372167.
Column k = 0 is A372169, labeled A372168 (non-covering A213434).
Column k = 1 is A372174, labeled A372171.
Column k = 1 is also the covering case of A372194, labeled A372172.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A053530, A137917, A137918, A140637, A144958, A322700, A370169.

a(21) onwards from Andrew Howroyd, Dec 29 2024

A105784 Number of different forests of unrooted trees, without isolated vertices, on n labeled nodes.

Original entry on oeis.org

0, 1, 3, 19, 155, 1641, 21427, 334377, 6085683, 126745435, 2975448641, 77779634571, 2241339267037, 70604384569005, 2414086713172695, 89049201691604881, 3525160713653081279, 149075374211881719939, 6707440248292609651513, 319946143503599791200675

Offset: 1

Washington Bomfim, Apr 21 2005

nonn

Number of labeled acyclic graphs covering n vertices. The unlabeled version is A144958. This is the covering case A001858. The connected case is A000272. - Gus Wiseman, Apr 28 2024

			a(4) = 19 because there are 19 different such forests on 4 labeled nodes: 4^2 are trees, 3 have two trees and none can have more than two trees.
From _Gus Wiseman_, Apr 28 2024: (Start)
Edge-sets of the a(2) = 1 through a(4) = 19 forests:
    12    12,13    12,34
          12,23    13,24
          13,23    14,23
                   12,13,14
                   12,13,24
                   12,13,34
                   12,14,23
                   12,14,34
                   12,23,24
                   12,23,34
                   12,24,34
                   13,14,23
                   13,14,24
                   13,23,24
                   13,23,34
                   13,24,34
                   14,23,24
                   14,23,34
                   14,24,34
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..150

Cf. A033185, A105599.
The connected case is A000272, rooted A000169.
This is the covering case of A001858, unlabeled A005195.
The unlabeled version is A144958.
For triangles instead of cycles we have A372168, covering case of A213434.
For a unique cycle we have A372195, covering case of A372193.
A002807 counts cycles in a complete graph.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A372170 counts simple graphs by triangles, covering A372167.
Cf. A053530, A054548, A137916, A137917, A322661, A367863, A372169, A372171, A372176, A372191.

b:= n-> add(add(binomial(m, j) *binomial(n-1, n-m-j)
        *n^(n-m-j) *(m+j)!/ (-2)^j, j=0..m)/m!, m=0..n):
a:= n-> add(b(k) *(-1)^(n-k) *binomial(n, k), k=0..n):
seq(a(n), n=1..17);  # Alois P. Heinz, Sep 10 2008

Unprotect[Power]; 0^0 = 1; b[n_] := Sum[Sum[Binomial[m, j]*Binomial[n-1, n -m-j]*n^(n-m-j)*(m+j)!/(-2)^j, {j, 0, m}]/m!, {m, 0, n}]; a[n_] := Sum[ b[k]*(-1)^(n-k)*Binomial[n, k], {k, 0, n}]; Table[a[n], {n, 1, 17}] (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)

a(n)= sum N/D over all the partitions of n: 1K1 + 2K2 + ... + nKn, with smallest part greater than 1, where N = n!*Product_{i=1..n}i^((i-2)Ki) and D = Product_{i=1..n}(Ki!(i!)^Ki).
Inverse binomial transform of A001858. E.g.f.: exp(-x-LambertW(-x) -LambertW(-x)^2/2). - Vladeta Jovovic, Apr 22 2005
a(n) ~ exp(-exp(-1)+1/2) * n^(n-2). - Vaclav Kotesovec, Aug 16 2013

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

A372168 Number of triangle-free simple labeled graphs covering n vertices.

Original entry on oeis.org

1, 0, 1, 3, 22, 237, 3961, 99900, 3757153, 208571691, 16945953790, 1999844518737, 340422874696873, 83041703920313712, 28850117307732482737, 14191512425207950473867, 9829313296102303971441502

Offset: 0

Gus Wiseman, Apr 23 2024

The unlabeled version is A372169.

			The a(4) = 22 graphs are:
  12-34
  13-24
  14-23
  12-13-14
  12-13-24
  12-13-34
  12-14-23
  12-14-34
  12-23-24
  12-23-34
  12-24-34
  13-14-23
  13-14-24
  13-23-24
  13-23-34
  13-24-34
  14-23-24
  14-23-34
  14-24-34
  12-13-24-34
  12-14-23-34
  13-14-23-24

Eric Weisstein's World of Mathematics, Triangle-Free Graph

Dominated by A006129, unlabeled A002494.
For all cycles (not just triangles) we have A105784, unlabeled A144958.
Covering case of A213434 (column k = 0 of A372170, unlabeled A263340).
The connected case is A345218, unlabeled A024607.
Column k = 0 of A372167, unlabeled A372173.
The unlabeled version is A372169.
For a unique triangle we have A372171, non-covering A372172.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A054548 counts covering graphs by number of edges, unlabeled A370167.
Cf. A000272, A053530, A121251, A367862, A367863, A372191, A372174, A372175.

cys[y_]:=Select[Subsets[Union@@y,{3}],MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Union@@#==Range[n]&&Length[cys[#]]==0&]],{n,0,5}]

Binomial transform is A213434.

A372174 Number of unlabeled simple graphs covering n vertices with a unique triangle.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 16, 79, 424, 3098, 28616

Offset: 0

Gus Wiseman, Apr 24 2024

The labeled version is A372171.

Gus Wiseman, The a(3) = 1 through a(6) = 16 covering graphs with a unique triangle.

The non-covering version is column k = 1 of A263340, labeled A372170.
Case of A370167 with a unique triangle, labeled A054548.
For no triangles we have A372169, labeled A372168 (non-covering A213434).
The labeled version is A372171, column k = 1 of A372167.
Column k = 1 of A372173, labeled A372167.
For cycles (not just triangles) we have A372191, labeled A372195.
The non-covering version is A372194, labeled A372172.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A002494 counts unlabeled covering graphs, labeled A006129.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A053530, A137917, A137918, A140637, A144958, A370169.

First differences of A372194.

A372195 Number of labeled simple graphs covering n vertices with a unique undirected cycle of length > 2.

Original entry on oeis.org

0, 0, 0, 1, 15, 232, 3945, 75197, 1604974, 38122542, 1000354710, 28790664534, 902783451933, 30658102047787, 1121532291098765, 43985781899812395, 1841621373756094796, 82002075703514947236, 3869941339069299799884, 192976569550677042208068, 10139553075163838030949495

Offset: 0

Gus Wiseman, Apr 25 2024

nonn

An undirected cycle in a graph is a sequence of distinct vertices, up to rotation and reversal, such that there are edges between all consecutive elements, including the last and the first.

			The a(4) = 15 graphs:
  12,13,14,23
  12,13,14,24
  12,13,14,34
  12,13,23,24
  12,13,23,34
  12,13,24,34
  12,14,23,24
  12,14,23,34
  12,14,24,34
  12,23,24,34
  13,14,23,24
  13,14,23,34
  13,14,24,34
  13,23,24,34
  14,23,24,34

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

For no cycles we have A105784 (for triangles A372168, non-covering A213434), unlabeled A144958 (for triangles A372169).
Counting triangles instead of cycles gives A372171 (non-covering A372172), unlabeled A372174 (non-covering A372194).
The unlabeled version is A372191, non-covering A236570.
The non-covering version is A372193, column k = 1 of A372176.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A002807 counts cycles in a complete graph.
A006129 counts labeled graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
A372167 counts covering graphs by triangles (non-covering A372170), unlabeled A372173 (non-covering A263340).
Cf. A000169, A000272, A053530, A054548, A137916, A137917, A367863, A368597.

cyc[y_]:=Select[Join@@Table[Select[Join@@Permutations/@Subsets[Union@@y,{k}],And@@Table[MemberQ[Sort/@y,Sort[{#[[i]],#[[If[i==k,1,i+1]]]}]],{i,k}]&],{k,3,Length[y]}],Min@@#==First[#]&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[cyc[#]]==2&]],{n,0,5}]

seq(n)={my(w=lambertw(-x+O(x*x^n))); Vec(serlaplace(exp(-w-w^2/2-x)*(-log(1+w)/2 + w/2 - w^2/4)), -n-1)} \\ Andrew Howroyd, Jul 31 2024

Inverse binomial transform of A372193. - Andrew Howroyd, Jul 31 2024

a(7) onwards from Andrew Howroyd, Jul 31 2024

A372175 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with exactly 2k directed cycles of length > 2.

Original entry on oeis.org

1, 0, 1, 3, 1, 19, 15, 0, 6, 0, 0, 0, 1, 155, 232, 15, 190, 0, 0, 70, 50, 0, 0, 0, 0, 30, 15, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 24 2024

A directed cycle in a simple (undirected) graph is a sequence of distinct vertices, up to rotation, such that there are edges between all consecutive elements, including the last and the first.

			Triangle begins (zeros shown as dots):
  1
  .
  1
  3 1
  19 15 . 6 ... 1
  155 232 15 190 .. 70 50 .... 30 15 .......... 10 .............. 1
Row n = 4 counts the following graphs:
  12,34     12,13,14,23  .  12,13,14,23,24  .  .  .  12,13,14,23,24,34
  13,24     12,13,14,24     12,13,14,23,34
  14,23     12,13,14,34     12,13,14,24,34
  12,13,14  12,13,23,24     12,13,23,24,34
  12,13,24  12,13,23,34     12,14,23,24,34
  12,13,34  12,13,24,34     13,14,23,24,34
  12,14,23  12,14,23,24
  12,14,34  12,14,23,34
  12,23,24  12,14,24,34
  12,23,34  12,23,24,34
  12,24,34  13,14,23,24
  13,14,23  13,14,23,34
  13,14,24  13,14,24,34
  13,23,24  13,23,24,34
  13,23,34  14,23,24,34
  13,24,34
  14,23,24
  14,23,34
  14,24,34

Row lengths are A002807 + 1.
Row sums are A006129, unlabeled A002494.
Column k = 0 is A105784 (for triangles A372168, non-covering A213434), unlabeled A144958 (for triangles A372169).
Counting triangles instead of cycles gives A372167 (non-covering A372170), unlabeled A372173 (non-covering A263340).
The non-covering version is A372176.
Column k = 1 is A372195 (non-covering A372193, for triangles A372171), unlabeled A372191 (non-covering A236570, for triangles A372174).
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000272, A053530, A121251, A137916, A137917, A372172, A372194.

cycles[g_]:=Join@@Table[Select[Join@@Permutations /@ Subsets[Union@@g,{k}],Min@@#==First[#]&&And@@Table[MemberQ[Sort/@g,Sort[{#[[i]], #[[If[i==k,1,i+1]]]}]],{i,k}]&],{k,3,Length[g]}];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[cycles[#]]==2k&]], {n,0,5},{k,0,Length[cycles[Subsets[Range[n],{2}]]]/2}]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A372167 Irregular triangle read by rows where T(n,k) is the number of simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A372171 Number of labeled simple graphs covering n vertices with a unique triangle.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A372173 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A105784 Number of different forests of unrooted trees, without isolated vertices, on n labeled nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

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

A372168 Number of triangle-free simple labeled graphs covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A372174 Number of unlabeled simple graphs covering n vertices with a unique triangle.

Views

Author

Keywords

Comments

Links