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

Links

Table of n, a(n) for n=0..19.

Formula

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

Example

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

Mathematica

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

Prog

(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

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.

Sequence in context: A027335 A133686 A369193 * A153525 A153553 A334617

Adjacent sequences: A369189 A369190 A369191 * A369193 A369194 A369195

Keyword

nonn

Author

Gus Wiseman, Jan 17 2024

Status

approved