A054548 -id:A054548 - cp's OEIS frontend

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

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

A370167 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with k = 0..binomial(n,2) edges.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 2, 1, 1, 0, 0, 0, 1, 4, 5, 5, 4, 2, 1, 1, 0, 0, 0, 1, 3, 9, 15, 20, 22, 20, 14, 9, 5, 2, 1, 1, 0, 0, 0, 0, 1, 6, 20, 41, 73, 110, 133, 139, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 0, 0, 0, 0, 1, 3, 15, 50, 124, 271, 515, 832, 1181, 1460, 1581, 1516, 1291, 970, 658, 400, 220, 114, 56, 24, 11, 5, 2, 1, 1

Offset: 0

Gus Wiseman, Feb 15 2024

			Triangle begins:
  1
  0
  0  1
  0  0  1  1
  0  0  1  2  2  1  1
  0  0  0  1  4  5  5  4  2  1  1
  0  0  0  1  3  9 15 20 22 20 14  9  5  2  1  1

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)

Column sums are A000664.
Row sums are A002494.
This is the covering case of A008406, labeled A084546.
The labeled version is A054548, row sums A006129, column sums A121251.
The connected case is A054924, row sums A001349, column sums A002905.
The labeled connected case is A062734, with loops A369195.
The connected case with loops is A283755, row sums A054921.
The labeled version w/ loops is A369199, row sums A322661, col sums A173219.
Cf. A000666, A006125, A006649, A054547, A066383, A322700.

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

\\ G(n) defined in A008406.
row(n)={Vecrev(G(n)-if(n>0, G(n-1)), binomial(n,2)+1)}
{ for(n=0, 7, print(row(n))) } \\ Andrew Howroyd, Feb 19 2024

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

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.

A372172 Number of labeled simple graphs on n vertices with exactly one triangle.

Original entry on oeis.org

0, 0, 0, 1, 16, 290, 6980, 235270, 11298056, 777154308, 76560083040

Offset: 0

Gus Wiseman, Apr 24 2024

The unlabeled version is A372194.

			The a(4) = 16 graphs:
  12,13,23
  12,14,24
  13,14,34
  23,24,34
  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

For no triangles we have A213434, covering A372168 (unlabeled A372169).
Column k = 1 of A372170, unlabeled A263340.
The covering case is A372171, unlabeled A372174.
For all cycles (not just triangles) we have A372193, covering A372195.
The unlabeled version is A372194.
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.
A372167 counts covering graphs by triangles, unlabeled A372173.
Cf. A000272, A105784, A121251, A137916, A236570, A372176.

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}]], Length[cys[#]]==1&]],{n,0,5}]

Binomial transform of A372171.

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

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.

A372193 Number of labeled simple graphs on n vertices with a unique cycle of length > 2.

Original entry on oeis.org

0, 0, 0, 1, 19, 317, 5582, 108244, 2331108, 55636986, 1463717784, 42182876763, 1323539651164, 44955519539963, 1644461582317560, 64481138409909506, 2698923588248208224, 120133276796015812548, 5667351458582453925696, 282496750694780020437765, 14837506263979393796687088

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) = 19 graphs:
  12,13,23
  12,14,24
  13,14,34
  23,24,34
  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 A001858 (covering A105784), unlabeled A005195 (covering A144958).
Counting triangles instead of cycles gives A372172 (non-covering A372171), unlabeled A372194 (non-covering A372174).
The unlabeled version is A236570, non-covering A372191.
The covering case is A372195, column k = 1 of A372175.
A000088 counts unlabeled graphs, labeled A006125.
A002807 counts cycles in a complete graph.
A006129 counts labeled graphs, unlabeled A002494.
A372167 counts graphs by triangles, non-covering A372170.
A372173 counts unlabeled graphs by triangles, non-covering A263340.
Cf. A000272, A054548, A057500, A121251, A137916, A213434, A322661, A372169, A372176.

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}]], Length[cyc[#]]==2&]],{n,0,5}]

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

E.g.f.: B(x)*C(x) where B(x) is the e.g.f. of A057500 and C(x) is the e.g.f. of A001858. - Andrew Howroyd, Jul 31 2024

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

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

cp's OEIS Frontend

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

A370167 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with k = 0..binomial(n,2) edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A372172 Number of labeled simple graphs on n vertices with exactly one triangle.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments