A084546 -id:A084546 - cp's OEIS frontend

A008406 Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2).

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 1, 2, 5, 9, 15, 21, 24, 24, 21, 15, 9, 5, 2, 1, 1, 1, 1, 2, 5, 10, 21, 41, 65, 97, 131, 148, 148, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1, 1, 1, 2, 5, 11, 24, 56, 115, 221, 402, 663, 980, 1312, 1557, 1646, 1557

Offset: 1

N. J. A. Sloane, Mar 15 1996

T(n,k)=1 for n>=2 with k=0, k=1, k=n*(n-1)/2-1 and k=n*(n-1)/2 (therefore the quadruple {1,1,1,1} marks the transition to the next sublist for a given number of vertices (n>2)). [Edited by Peter Munn, Mar 20 2021]

			Triangle begins:
1,
1,1,
1,1,1,1,
1,1,2,3,2,1,1, [graphs with 4 nodes and from 0 to 6 edges]
1,1,2,4,6,6,6,4,2,1,1,
1,1,2,5,9,15,21,24,24,21,15,9,5,2,1,1,
1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,21,10,5,2,1,1,
...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

R. W. Robinson, Rows 1 to 20 of triangle, flattened
Leonid Bedratyuk, A new formula for the generating function of the numbers of simple graphs, arXiv:1512.06355 [math.CO], 2015.
FindStat - Combinatorial Statistic Finder, The number of edges of a graph.
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017) Table 65.
Sriram V. Pemmaraju, Combinatorica 2.0
Marko R. Riedel, Number of distinct connected digraphs
Gordon Royle, Small graphs
S. S. Skiena, Generating graphs
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Overview of the 12 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 11
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 12
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 19.
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Simple Graph
A. E. Yurtsun, Principles of enumeration of the number of graphs, Ukrainian Mathematical Journal, January-February, 1967, Volume 19, Issue 1, pp 123-125, DOI 10.1007/BF01085184.

Row sums give A000088.
Cf. A046742, A046751, A000717, A001432, A001431, A001430, A001433, A001434, A048179, A048180 etc.
Cf. also A039735, A002905, A054924 (connected), A084546 (labeled graphs).
Row lengths: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664.
Cf. also A000055.

seq(seq(GraphTheory:-NonIsomorphicGraphs(v,e),e=0..v*(v-1)/2),v=1..9); # Robert Israel, Dec 22 2015

<< Combinatorica`; Table[CoefficientList[GraphPolynomial[n, x], x], {n, 8}] // Flatten (* Eric W. Weisstein, Mar 20 2013 *)
<< Combinatorica`; Table[NumberOfGraphs[v, e], {v, 8}, {e, 0, Binomial[v, 2]}] // Flatten (* Eric W. Weisstein, May 17 2017 *)
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_, t_] := Product[Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/ g]^g,{j, 1, i-1}], {i, 2, Length[v]}]*Product[c = v[[i]]; t[c]^Quotient[ c-1, 2]*If[OddQ[c], 1, t[c/2]], {i, 1, Length[v]}];
row[n_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, 1 + x^#&], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x]&;
Array[row, 8] // Flatten (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v,t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i],v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
G(n, A=0) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i+A)); s/n!}
{ for(n=1, 7, print(Vecrev(G(n)))) } \\ Andrew Howroyd, Oct 22 2019, updated  Jan 09 2024

def T(n,k):
    return len(list(graphs(n, size=k)))
# Ralf Stephan, May 30 2014

O.g.f. for n-th row: 1/n! Sum_g det(1-g z^2)/det(1-g z) where g runs through the natural matrix representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, Sep 23 2014

Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002

Text belonging in a different sequence deleted by Peter Munn, Mar 20 2021

A116508 a(n) = C( C(n,2), n).

Original entry on oeis.org

1, 0, 0, 1, 15, 252, 5005, 116280, 3108105, 94143280, 3190187286, 119653565850, 4922879481520, 220495674290430, 10682005290753420, 556608279578340080, 31044058215401404845, 1845382436487682488000, 116475817125419611477660, 7779819801401934344268210

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Mar 21 2006

a(n) is the number of simple labeled graphs with n nodes and n edges. - Geoffrey Critzer, Nov 02 2014

These graphs are not necessarily covering, but the covering case is A367863, unlabeled A006649, and the unlabeled version is A001434. - Gus Wiseman, Dec 22 2023

			a(5) = C(C(5,2),5) = C(10,5) = 252.

Alois P. Heinz, Table of n, a(n) for n = 0..370

Main diagonal of A084546.
The unlabeled version is A001434, covering case A006649.
The connected case is A057500, unlabeled A001429.
For set-systems we have A136556, covering case A054780.
The covering case is A367863.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A133686 counts graphs satisfying a strict AOC, connected A129271.
A367867 counts graphs contradicting a strict AOC, connected A140638.
Cf. A001187, A003465, A143543, A305000, A367916, A367917.

[0] cat [(Binomial(Binomial(n+2, n), n+2)): n in [0..20]]; // Vincenzo Librandi, Nov 03 2014

a:= n-> binomial(binomial(n, 2), n):
seq(a(n), n=0..20);

nn = 18; f[x_, y_] :=
Sum[(1 + y)^Binomial[n, 2] x^n/n!, {n, 1, nn}]; Table[
n! Coefficient[Series[f[x, y], {x, 0, nn}], x^n y^n], {n, 1, nn}] (* Geoffrey Critzer, Nov 02 2014 *)
Table[Length[Subsets[Subsets[Range[n],{2}],{n}]],{n,0,5}] (* Gus Wiseman, Dec 22 2023 *)
Table[SeriesCoefficient[(1 + x)^(n*(n-1)/2), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Aug 06 2025 *)

from math import comb
def A116508(n): return comb(n*(n-1)>>1,n) # Chai Wah Wu, Jul 02 2024

[(binomial(binomial(n+2,n),n+2)) for n in range(-1, 17)] # Zerinvary Lajos, Nov 30 2009

a(n) ~ exp(n - 2) * n^(n - 1/2) / (sqrt(Pi) * 2^(n + 1/2)). - Vaclav Kotesovec, May 19 2020

a(n) = [x^n] (1+x)^(n*(n-1)/2). - Vaclav Kotesovec, Aug 06 2025

a(0)=1 prepended by Alois P. Heinz, Feb 02 2024

A054548 Triangular array giving number of labeled graphs on n unisolated nodes and k=0...n*(n-1)/2 edges.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 3, 1, 0, 0, 3, 16, 15, 6, 1, 0, 0, 0, 30, 135, 222, 205, 120, 45, 10, 1, 0, 0, 0, 15, 330, 1581, 3760, 5715, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 0, 0, 0, 0, 315, 4410, 23604, 73755, 159390, 259105, 331716, 343161, 290745, 202755, 116175

Offset: 0

Vladeta Jovovic, Apr 09 2000

			From _Gus Wiseman_, Feb 14 2024: (Start)
Triangle begins:
   1
   0
   0   1
   0   0   3   1
   0   0   3  16  15   6   1
   0   0   0  30 135 222 205 120  45  10   1
Row n = 4 counts the following graphs:
  .  .  12-34  12-13-14  12-13-14-23  12-13-14-23-24  12-13-14-23-24-34
        13-24  12-13-24  12-13-14-24  12-13-14-23-34
        14-23  12-13-34  12-13-14-34  12-13-14-24-34
               12-14-23  12-13-23-24  12-13-23-24-34
               12-14-34  12-13-23-34  12-14-23-24-34
               12-23-24  12-13-24-34  13-14-23-24-34
               12-23-34  12-14-23-24
               12-24-34  12-14-23-34
               13-14-23  12-14-24-34
               13-14-24  12-23-24-34
               13-23-24  13-14-23-24
               13-23-34  13-14-23-34
               13-24-34  13-14-24-34
               14-23-24  13-23-24-34
               14-23-34  14-23-24-34
               14-24-34
(End)

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, Page 29, Exercise 1.4.

Michael De Vlieger, Table of n, a(n) for n = 0..10700
A. N. Bhavale and B. N. Waphare, Basic retracts and counting of lattices, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.
Ashok Nivrutti Bhavale, Equivalence of labeled graphs and lattices, arXiv:2501.05064 [math.CO], 2025. See pp. 1-2, 13.
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4.

Row sums give A006129. Cf. A054547.
The connected case is A062734, with loops A369195.
This is the covering case of A084546.
Column sums are A121251, with loops A173219.
The version with loops is A369199, row sums A322661.
The unlabeled version is A370167, row sums A002494.
A006125 counts simple graphs; also loop-graphs if shifted left.
Cf. A000666, A006649, A062740, A066383, A121252, A133686, A322700, A368597, A369196, A369197.

nn=5; s=Sum[(1+y)^Binomial[n,2]  x^n/n!, {n,0,nn}]; Range[0,nn]! CoefficientList[Series[ s Exp[-x], {x,0,nn}], {x,y}] //Grid  (* returns triangle indexed at n = 0, Geoffrey Critzer, Oct 07 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}],{k}],Union@@#==Range[n]&]],{n,0,5},{k,0,Binomial[n,2]}] (* Gus Wiseman, Feb 14 2024 *)

T(n, k) = Sum_{i=0..n} (-1)^(n-i)*C(n, i)*C(C(i, 2), k), k=0...n*(n-1)/2.

E.g.f.: exp(-x)*Sum_{n>=0} (1 + y)^C(n,2)*x^n/n!. - Geoffrey Critzer, Oct 07 2012

a(0) prepended by Gus Wiseman, Feb 14 2024

A014068 a(n) = binomial(n*(n+1)/2, n).

Original entry on oeis.org

1, 1, 3, 20, 210, 3003, 54264, 1184040, 30260340, 886163135, 29248649430, 1074082795968, 43430966148115, 1917283000904460, 91748617512913200, 4730523156632595024, 261429178502421685800, 15415916972482007401455, 966121413245991846673830, 64123483527473864490450300

Offset: 0

N. J. A. Sloane

nonn

Product of next n numbers divided by product of first n numbers. E.g., a(4) = (7*8*9*10)/(1*2*3*4)= 210. - Amarnath Murthy, Mar 22 2004

Also the number of labeled loop-graphs with n vertices and n edges. The covering case is A368597. - Gus Wiseman, Jan 25 2024

			From _Gus Wiseman_, Jan 25 2024: (Start)
The a(0) = 1 through a(3) = 20 loop-graph edge-sets (loops shown as singletons):
  {}  {{1}}  {{1},{2}}    {{1},{2},{3}}
             {{1},{1,2}}  {{1},{2},{1,2}}
             {{2},{1,2}}  {{1},{2},{1,3}}
                          {{1},{2},{2,3}}
                          {{1},{3},{1,2}}
                          {{1},{3},{1,3}}
                          {{1},{3},{2,3}}
                          {{2},{3},{1,2}}
                          {{2},{3},{1,3}}
                          {{2},{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}}
(End)

Harvey P. Dale, Table of n, a(n) for n = 0..370
R. Mestrovic, Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862-2011), arXiv:1111.3057 [math.NT], 2011.
Eric Weisstein's World of Mathematics, Graph Loop.

Cf. A000217, A022915, A135860, A135861, A135862.
Diagonal of A084546.
Without loops we have A116508, covering A367863, unlabeled A006649.
Allowing edges of any positive size gives A136556, covering A054780.
The covering case is A368597.
The unlabeled version is A368598, covering A368599.
The connected case is A368951.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 (shifted left) counts loop-graphs, covering A322661.
A006129 counts covering simple graphs, connected A001187.
A058891 counts set-systems, unlabeled A000612.
Cf. A000085, A000272, A057500, A333331, A368596, A368730.

[Binomial(Binomial(n+1,2), n): n in [0..40]]; // G. C. Greubel, Feb 19 2022

Binomial[First[#],Last[#]]&/@With[{nn=20},Thread[{Accumulate[ Range[ 0,nn]], Range[ 0,nn]}]] (* Harvey P. Dale, May 27 2014 *)

from math import comb
def A014068(n): return comb(comb(n+1,2),n) # Chai Wah Wu, Jul 14 2024

[(binomial(binomial(n+1, n-1), n)) for n in range(20)] # Zerinvary Lajos, Nov 30 2009

For n >= 1, Product_{k=1..n} a(k) = A022915(n). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 08 2001
For n > 0, a(n) = A022915(n)/A022915(n-1). - Gerald McGarvey, Jul 26 2004
a(n) = binomial(T(n+1), T(n)) where T(n) = the n-th triangular number. - Amarnath Murthy, Jul 14 2005
a(n) = binomial(binomial(n+2, n), n+1) for n >= -1. - Zerinvary Lajos, Nov 30 2009
From Peter Bala, Feb 27 2020: (Start)
a(p) == (p + 1)/2 ( mod p^3 ) for prime p >= 5 (apply Mestrovic, equation 37).
Conjectural: a(2*p) == p*(2*p + 1) ( mod p^4 ) for prime p >= 5. (End)
a(n) = A084546(n,n). - Gus Wiseman, Jan 25 2024
a(n) = [x^n] (1+x)^(n*(n+1)/2). - Vaclav Kotesovec, Aug 06 2025

A369199 Irregular triangle read by rows where T(n,k) is the number of labeled loop-graphs covering n vertices with k edges.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 1, 0, 0, 6, 17, 15, 6, 1, 0, 0, 3, 46, 150, 228, 206, 120, 45, 10, 1, 0, 0, 0, 45, 465, 1803, 3965, 5835, 6210, 4955, 2998, 1365, 455, 105, 15, 1, 0, 0, 0, 15, 645, 5991, 27364, 79470, 165555, 264050, 334713, 344526, 291200, 202860, 116190, 54258, 20349, 5985, 1330, 210, 21, 1

Offset: 0

Gus Wiseman, Jan 18 2024

			Triangle begins:
   1
   0   1
   0   1   3   1
   0   0   6  17  15   6   1
   0   0   3  46 150 228 206 120  45  10   1
Row n = 3 counts the following loop-graphs (loops shown as singletons):
  {1,23}   {1,2,3}     {1,2,3,12}    {1,2,3,12,13}   {1,2,3,12,13,23}
  {2,13}   {1,2,13}    {1,2,3,13}    {1,2,3,12,23}
  {3,12}   {1,2,23}    {1,2,3,23}    {1,2,3,13,23}
  {12,13}  {1,3,12}    {1,2,12,13}   {1,2,12,13,23}
  {12,23}  {1,3,23}    {1,2,12,23}   {1,3,12,13,23}
  {13,23}  {1,12,13}   {1,2,13,23}   {2,3,12,13,23}
           {1,12,23}   {1,3,12,13}
           {1,13,23}   {1,3,12,23}
           {2,3,12}    {1,3,13,23}
           {2,3,13}    {1,12,13,23}
           {2,12,13}   {2,3,12,13}
           {2,12,23}   {2,3,12,23}
           {2,13,23}   {2,3,13,23}
           {3,12,13}   {2,12,13,23}
           {3,12,23}   {3,12,13,23}
           {3,13,23}
           {12,13,23}

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

The version without loops is A054548.
This is the covering case of A084546.
Column sums are A173219.
Row sums are A322661, unlabeled A322700.
The connected case is A369195, without loops A062734.
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.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000666, A006649, A062740, A066383, A133686, A368597, A369196, A369197.

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

T(n)={[Vecrev(p) | p<-Vec(serlaplace(exp(-x + O(x*x^n))*(sum(j=0, n, (1 + y)^binomial(j+1, 2)*x^j/j!)))) ]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Feb 02 2024

E.g.f.: exp(-x) * (Sum_{j >= 0} (1 + y)^binomial(j+1, 2)*x^j/j!). - Andrew Howroyd, Feb 02 2024

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

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

Original entry on oeis.org

1, 1, 2, 7, 1, 41, 16, 6, 0, 1, 388, 290, 195, 70, 40, 30, 0, 10, 0, 0, 1, 5789, 6980, 6910, 4560, 3030, 2292, 1230, 780, 600, 180, 236, 60, 45, 60, 0, 0, 15, 0, 0, 0, 1, 133501, 235270, 313705, 302505, 260890, 222509, 174615, 126780, 102970, 67165, 50134, 37485, 20370, 17990, 11445, 6552, 4515, 3570, 1680, 1785, 154, 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
     1
     2
     7    1
    41   16    6    0    1
   388  290  195   70   40   30    0   10    0    0    1
   ...
For example, the T(4,1) = 16 graphs are:
  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

Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)

Row sums are A006125, covering A006129.
Row lengths are A050407.
Counting edges instead of triangles gives A084546, covering A054548.
Column k = 0 is A213434, covering A372168.
The unlabeled version is A263340.
The covering case is A372167, unlabeled A372173.
Column k = 1 is A372172, covering A372171.
For all cycles (not just triangles) we have A372176, covering A372175.
A001858 counts acyclic graphs, unlabeled A005195.
A367867 counts non-choosable graphs, covering A367868.
A372193 counts unicyclic graphs, unlabeled A236570, covering A372191.
Cf. A000088, A000272, A002494, A006785, A053530, A062734, A121251, A372194.

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

Binomial transform of columns of A372167.

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

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

Original entry on oeis.org

1, 1, 2, 7, 1, 38, 19, 0, 6, 0, 0, 0, 1, 291, 317, 15, 220, 0, 0, 70, 55, 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 25 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
   2
   7 1
   38 19 . 6 ... 1
   291 317 15 220 .. 70 55 .... 30 15 ........ 10 ............... 1
The T(4,3) = 6 graphs:
  12,13,14,23,24
  12,13,14,23,34
  12,13,14,24,34
  12,13,23,24,34
  12,14,23,24,34
  13,14,23,24,34

Column k = 0 is A001858 (unlabeled A005195), covering A105784.
Row lengths are A002807 + 1.
Row sums are A006125, unlabeled A000088.
Counting edges instead of cycles gives A084546 (covering A054548), unlabeled A008406 (covering A370167).
Counting triangles instead of cycles gives A372170 (covering A372167), unlabeled A263340 (covering A372173).
The covering case is A372175.
Column k = 1 is A372193 (covering A372195), unlabeled A236570.
A006129 counts graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000272, A053530, A137916, A144958, A213434, A367863, A372168, A372169, A372171, A372172, A372191.

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[#]]==2k&]], {n,0,4}, {k,0,Length[cyc[Subsets[Range[n],{2}]]]/2}]

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

A234249 Number of ways to choose 4 points in an n X n X n triangular grid.

Original entry on oeis.org

15, 210, 1365, 5985, 20475, 58905, 148995, 341055, 720720, 1426425, 2672670, 4780230, 8214570, 13633830, 21947850, 34389810, 52602165, 78738660, 115584315, 166695375, 236561325, 330791175, 456326325, 621682425, 837222750, 1115465715, 1471429260, 1923014940

Offset: 3

Heinrich Ludwig, Feb 02 2014

Sequence is column #5 of A084546: a(n) = A084546(n+1, 4).
All elements of the sequence are multiples of 15.
a(n-1) is the number of chiral pairs of colorings of the 8 cubic facets of a tesseract (hypercube) with Schläfli symbol {4,3,3} or of the 8 vertices of a hyperoctahedron with Schläfli symbol {3,3,4}. Both figures are regular 4-D polyhedra and they are mutually dual. Each member of a chiral pair is a reflection, but not a rotation, of the other. - Robert A. Russell, Oct 20 2020

Heinrich Ludwig, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A084546, A050534 (number of ways to choose 2 points), A093566 (3 points), A231653.
Cf. A337956 (oriented), A337956 (unoriented), A337956 (achiral) colorings, A331356 (hyperoctahedron edges, tesseract faces), A331360 (hyperoctahedron faces, tesseract edges), A337954 (hyperoctahedron facets, tesseract vertices).
Other polychora: A000389 (5-cell), A338950 (24-cell), A338966 (120-cell, 600-cell).
Row 4 of  A325006 (orthotope facets, orthoplex vertices).

A234249:=n->n*(n + 1)*(n - 1)*(n + 2)*(n - 2)*(n + 3)*(n^2 + n - 4)/384: seq(A234249(n), n=3..40); # Wesley Ivan Hurt, Jan 10 2017

Table[Binomial[Binomial[n,2],4], {n,4,30}] (* Robert A. Russell, Oct 20 2020 *)

Vec(-15*x^3*(x^2+5*x+1)/(x-1)^9 + O(x^100)) \\ Colin Barker, Feb 02 2014

a(n) = n*(n + 1)*(n - 1)*(n + 2)*(n - 2)*(n + 3)*(n^2 + n - 4)/384.
a(n) = C(C(n + 1, 2), 4).
G.f.: -15*x^3*(x^2+5*x+1) / (x-1)^9. - Colin Barker, Feb 02 2014
From Robert A. Russell, Oct 20 2020: (Start)
a(n-1) = 15*C(n,4) + 135*C(n,5) + 330*C(n,6) + 315*C(n,7) + 105*C(n,8), where the coefficient of C(n,k) is the number of chiral pairs of colorings using exactly k colors.
a(n-1) = A337956(n) - A337957(n) = (A337956(n) - A337958(n)) / 2 = A337957(n) - A337958(n).
a(n-1) = A325006(4,n). (End)

cp's OEIS Frontend

A008406 Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A116508 a(n) = C( C(n,2), n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

Sage

Formula

Extensions

A054548 Triangular array giving number of labeled graphs on n unisolated nodes and k=0...n*(n-1)/2 edges.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A014068 a(n) = binomial(n*(n+1)/2, n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Python

Sage

Formula

A369199 Irregular triangle read by rows where T(n,k) is the number of labeled loop-graphs covering n vertices with k edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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