A369192 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

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

(list; graph; refs; listen; history; text; internal format)

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