A006125 -id:A006125 - cp's OEIS frontend

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.

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

A053549 Number of labeled rooted connected graphs.

Original entry on oeis.org

0, 1, 2, 12, 152, 3640, 160224, 13063792, 2012388736, 596666619648, 344964885948160, 392058233038486784, 880255154481199466496, 3916538634445633156373504, 34603083354426212294072477696, 607915214065957203519146330173440

Offset: 0

N. J. A. Sloane, Jan 16 2000

nonn

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 10, R_p.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.20, G(x).

T. D. Noe, Table of n, a(n) for n=0..50

Cf. A006125.

q:=30; m:=20; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( (&+[2^Binomial(j, 2)*x^j/Factorial(j-1): j in [1..q]])/(&+[2^Binomial(k, 2)*x^k/Factorial(k):k in [0..q]]) )); [0] cat [Factorial(n)*b[n]: n in [1..m-1]]; // G. C. Greubel, May 16 2019

add(2^binomial(n,2)*x^n/(n-1)!,n=1..31)/add(2^binomial(n,2)*x^n/n!,n=0..31);

f[x_, lim_] := Sum[2^Binomial[n, 2]*x^n/(n - 1)!, {n, 1, lim}] / Sum[2^Binomial[n, 2]*x^n/n!, {n, 0, lim}]; nn = 15; Range[0, nn]! CoefficientList[Series[f[x, nn], {x, 0, nn}], x] (* T. D. Noe, Oct 21 2011 *)

q=30; my(x='x+O('x^20)); concat([0], Vec(serlaplace( sum(j=1,q, 2^binomial(j, 2)*x^j/(j-1)!)/(sum(k=0,q,2^binomial(k, 2)*x^k/k!)) ))) \\ G. C. Greubel, May 16 2019

q=30; m = 20; T = taylor(sum(2^binomial(j, 2)*x^j/factorial(j-1) for j in (1..q))/(sum(2^binomial(k, 2)*x^k/factorial(k) for k in (0..q))), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # G. C. Greubel, May 16 2019

E.g.f.: (Sum_{n>1} 2^binomial(n, 2)*x^n/(n-1)!)/(Sum_{n>=0} 2^binomial(n, 2)*x^n/n!).

a(n) = n * A001187(n).

A261919 Number of n-node unlabeled graphs without isolated nodes or endpoints (i.e., no nodes of degree 0 or 1).

Original entry on oeis.org

1, 0, 0, 1, 3, 11, 62, 510, 7459, 197867, 9808968, 902893994, 153723380584, 48443158427276, 28363698856991892, 30996526139142442460, 63502034434187094606966, 244852545450108200518282934, 1783161611521019613186341526720, 24603891216946828886755056314074748

Offset: 0

N. J. A. Sloane, Sep 15 2015

nonn

			From _Gus Wiseman_, Aug 15 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(5) = 11 graphs (empty columns not shown):
  {}  {12,13,23}  {12,13,24,34}        {12,13,24,35,45}
                  {13,14,23,24,34}     {12,14,25,34,35,45}
                  {12,13,14,23,24,34}  {12,15,25,34,35,45}
                                       {13,14,23,24,35,45}
                                       {12,13,24,25,34,35,45}
                                       {13,15,24,25,34,35,45}
                                       {14,15,24,25,34,35,45}
                                       {12,13,15,24,25,34,35,45}
                                       {14,15,23,24,25,34,35,45}
                                       {13,14,15,23,24,25,34,35,45}
                                       {12,13,14,15,23,24,25,34,35,45}
(End)

F. Harary, Graph Theory, Wiley, 1969. See illustrations in Appendix 1.

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..26 from Max Alekseyev)
N. J. A. Sloane, Illustration of a(0)-a(5) [Ignore the graphs with isolated nodes]

Cf. A004108 (connected version), A004110 (version allowing isolated nodes).
The labeled version is A100743.
Cf. A003227, A006125, A007146, A059166, A095983, A322396.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1-x^p[[i]], {i, 1, Length[p]}], x, n-k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}]; b[0] = 1;
a[n_] := b[n] - b[n-1];
a /@ Range[0, 19] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd in A004110 *)

First differences of A004110: a(n) = A004110(n)-A004110(n-1).

Euler transform of A004108, if we assume A004108(1) = 0. - Gus Wiseman, Aug 15 2019

a(1)-a(11) computed by Brendan McKay, Sep 15 2015
a(12)-a(26) computed from A004110 by Max Alekseyev, Sep 16 2015
a(0) = 1 prepended by Gus Wiseman, Aug 15 2019

A326788 BII-numbers of simple labeled graphs.

Original entry on oeis.org

0, 4, 16, 20, 32, 36, 48, 52, 256, 260, 272, 276, 288, 292, 304, 308, 512, 516, 528, 532, 544, 548, 560, 564, 768, 772, 784, 788, 800, 804, 816, 820, 2048, 2052, 2064, 2068, 2080, 2084, 2096, 2100, 2304, 2308, 2320, 2324, 2336, 2340, 2352, 2356, 2560, 2564

Offset: 1

Gus Wiseman, Jul 25 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

Also numbers whose binary indices all belong to A018900.

			The sequence of all simple labeled graphs together with their BII-numbers begins:
    0: {}
    4: {{1,2}}
   16: {{1,3}}
   20: {{1,2},{1,3}}
   32: {{2,3}}
   36: {{1,2},{2,3}}
   48: {{1,3},{2,3}}
   52: {{1,2},{1,3},{2,3}}
  256: {{1,4}}
  260: {{1,2},{1,4}}
  272: {{1,3},{1,4}}
  276: {{1,2},{1,3},{1,4}}
  288: {{2,3},{1,4}}
  292: {{1,2},{2,3},{1,4}}
  304: {{1,3},{2,3},{1,4}}
  308: {{1,2},{1,3},{2,3},{1,4}}
  512: {{2,4}}
  516: {{1,2},{2,4}}
  528: {{1,3},{2,4}}
  532: {{1,2},{1,3},{2,4}}

Cf. A000120, A006125, A006129, A018900, A048793, A062880, A070939, A309356 (same for MM-numbers), A322551, A326031, A326702.

Other BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,100],SameQ[2,##]&@@Length/@bpe/@bpe[#]&]

A369146 Number of unlabeled loop-graphs with up to n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 8, 60, 471, 4911, 78797, 2207405, 113740613, 10926218807, 1956363413115, 652335084532025, 405402273420833338, 470568642161119515627, 1023063423471189429817807, 4178849203082023236054797465, 32168008290073542372004072630072, 468053896898117580623237189882068990

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

			The a(0) = 0 through a(3) = 8 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{1,2}}
                         {{1},{2},{3},{1,2}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{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 A000666, labeled A006125 (shifted).
For a unique choice we have A087803, labeled A088957.
The case without loops is A140637, labeled A367867 (covering A367868).
For exactly n edges we have A368835, labeled A368596.
The labeled complement is A368927, covering A369140.
The labeled version is A369141, covering A369142.
The complement is counted by A369145, covering A369200.
The covering case is A369147.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
Cf. A000088, A000612, A006649, A062740, A134964, A137917, A140638, A368600, A368984, A369199.

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],{1,2}]], Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,4}]

Partial sums of A369147.

a(n) = A000666(n) - A369145(n). - Andrew Howroyd, Feb 02 2024

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

cp's OEIS Frontend

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

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A053549 Number of labeled rooted connected graphs.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI