A369195 -id:A369195 - cp's OEIS frontend

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

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

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

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

cp's OEIS Frontend

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

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

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