A369192 Number of labeled simple graphs with n vertices and at most n edges (not necessarily covering).

1, 1, 2, 8, 57, 638, 9949, 198440, 4791323, 135142796, 4346814276, 156713948672, 6251579884084, 273172369790743, 12969420360339724, 664551587744173992, 36543412829258260135, 2146170890448154922648, 134053014635659737513358, 8872652968135849629240560

Offset: 0

Author

Gus Wiseman, Jan 17 2024

Keywords

• nonn

Examples

			The a(0) = 1 through a(3) = 8 graphs:
  {}  {}  {}       {}
          {{1,2}}  {{1,2}}
                   {{1,3}}
                   {{2,3}}
                   {{1,2},{1,3}}
                   {{1,2},{2,3}}
                   {{1,3},{2,3}}
                   {{1,2},{1,3},{2,3}}
		

Crossrefs

The version for loop-graphs is A066383, covering A369194.

The case of equality is A116508, covering A367863, also A367862.

The connected case is A129271, unlabeled A005703.

The covering case is A369191, minimal case A053530.

Counting only covered vertices gives A369193.

A006125 counts graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

A054548 counts graphs covering n vertices with k edges, with loops A369199.

A133686 counts choosable graphs, covering A367869.

A367867 counts non-choosable graphs, covering A367868.

Cf. A000169, A000272, A000666, A001187, A006649, A057500, A143543.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[#]<=n&]],{n,0,5}]

Python

from math import comb
def A369192(n): return sum(comb(comb(n,2),k) for k in range(n+1)) # Chai Wah Wu, Jul 14 2024

Formula

a(n) = Sum_{k=0..n} binomial(binomial(n,2),k).