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,7

References

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

Links

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.

R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4.

Formula

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

Example

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)

Mathematica

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

Crossrefs

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.

Sequence in context: A144357 A122848 A272481 * A059202 A244963 A144452

Adjacent sequences: A054545 A054546 A054547 * A054549 A054550 A054551

Keyword

easy,nonn,tabf

Author

Vladeta Jovovic, Apr 09 2000

Extensions

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

Status

approved