A370169 -id:A370169 - cp's OEIS frontend

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

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.

A263340 Triangle read by rows: T(n,k) is the number of graphs with n vertices containing k triangles.

Original entry on oeis.org

1, 1, 2, 3, 1, 7, 2, 1, 0, 1, 14, 7, 5, 2, 3, 1, 0, 1, 0, 0, 1, 38, 23, 28, 14, 18, 9, 7, 5, 4, 1, 4, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 107, 102, 141, 117, 123, 92, 80, 63, 49, 35, 35, 23, 15, 17, 10, 4, 9, 5, 2, 3, 3, 2, 2, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1

Offset: 0

Christian Stump, Oct 15 2015

Row sums give A000088.
First column is A006785.
Row lengths are 1 + binomial(n,3). - Geoffrey Critzer, Apr 13 2017

			Triangle begins:
  1;
  1;
  2;
  3,1;
  7,2,1,0,1;
  14,7,5,2,3,1,0,1,0,0,1;
  38,23,28,14,18,9,7,5,4,1,4,1,1,1,0,0,1,0,0,0,1;
  ...

Pontus von Brömssen, Rows n = 0..10, flattened
FindStat - Combinatorial Statistic Finder, The number of triangles of a graph.
Gus Wiseman, The graphs counted under row n = 5.

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

Table[Table[Count[Table[Tr[MatrixPower[AdjacencyMatrix[GraphData[{n, i}]], 3]]/6, {i, 1, NumberOfGraphs[n]}], k], {k, 0, Binomial[n, 3]}], {n, 1, 7}] (* Geoffrey Critzer, Apr 13 2017 *)

Row 7 from Geoffrey Critzer, Apr 13 2017

T(0,0)=1 prepended by Alois P. Heinz, Apr 13 2017

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

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 16, 43, 117, 319, 875, 2409, 6692, 18614, 52099, 146186, 411720, 1162295, 3289994, 9330913, 26517036, 75481622, 215201178, 614398459, 1756392061, 5026955216, 14403488345, 41311616835, 118601561506, 340795908579, 980078195995

Offset: 0

Gus Wiseman, Apr 27 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.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Gus Wiseman, The a(3) = 1 through a(6) = 16 covering graphs with a unique cycle.

For no cycles we have A144958 (non-covering A005195), labeled A105784 (non-covering A001858).
Counting triangles instead of cycles gives A372174 (non-covering A372194), labeled A372171 (non-covering A372172).
The non-covering version is A236570, labeled A372193.
The labeled version is A372195, column k = 1 of A372175.
A002807 counts cycles in a complete graph.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A372167 counts graphs by triangles, non-covering A372170.
A372173 counts unlabeled graphs by triangles (non-covering A263340).
A372176 counts labeled graphs by directed cycles.
Cf. A000055, A137916, A137917, A137918, A140637, A370167, A370169.

First differences of A236570.

a(7) onwards from Andrew Howroyd, Jul 31 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

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.

A370168 Number of unlabeled loop-graphs with n vertices and at most n edges.

Original entry on oeis.org

1, 2, 5, 13, 36, 102, 313, 994, 3318, 11536, 41748, 156735, 609973, 2456235, 10224216, 43946245, 194866898, 890575047, 4190997666, 20289434813, 100952490046, 515758568587, 2703023502100, 14518677321040, 79852871813827, 449333028779385, 2584677513933282

Offset: 0

Gus Wiseman, Feb 16 2024

nonn

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

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

The labeled version is A066383, covering A369194.
The case of equality is A368598, covering A368599.
The covering case is A370169, labeled A369194.
The loopless version is A370315, labeled A369192.
The covering loopless version is A370316, labeled A369191.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000666, A005703, A014068, A062740, A368597, A368927, A369141, A369196, A369197, 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}]],Length[#]<=n&]]],{n,0,5}]

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

a(7) 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

A370315 Number of unlabeled simple graphs with n possibly isolated vertices and up to n edges.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 54, 146, 436, 1372, 4577, 15971, 58376, 221876, 876012, 3583099, 15159817, 66248609, 298678064, 1387677971, 6637246978, 32648574416, 165002122350, 855937433641, 4553114299140, 24813471826280, 138417885372373, 789683693019999, 4603838061688077

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

			The a(1) = 1 through a(4) = 9 graph edge sets:
  {}  {}    {}          {}
      {12}  {12}        {12}
            {12-13}     {12-13}
            {12-13-23}  {12-34}
                        {12-13-14}
                        {12-13-23}
                        {12-13-24}
                        {12-13-14-23}
                        {12-13-24-34}

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

The case of exactly n edges is A001434, covering A006649.
The connected covering case is A005703, labeled A129271.
Partial row sums of A008406, covering A370167.
The labeled version is A369192.
The version with loops is A370168, labeled A066383.
The covering case is A370316, labeled A369191.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A000666, A322661, A322700, A369194, A369196, A369197, A369199, A370169.

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

a(n) = if(n<=1, n>=0, polcoef(G(n, O(x*x^n))/(1-x),n)) \\ G(n) defined in A008406. - Andrew Howroyd, Feb 20 2024

Sum of first n+1 terms of row n of A008406.

cp's OEIS Frontend

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

A263340 Triangle read by rows: T(n,k) is the number of graphs with n vertices containing k triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A370168 Number of unlabeled loop-graphs with n vertices and at most n edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica