A369193 Number of labeled simple graphs with n vertices and at most as many edges as covered (non-isolated) vertices.

1, 1, 2, 8, 57, 608, 8614, 151365, 3162353, 76359554, 2088663444, 63760182536, 2147325661180, 79051734050283, 3157246719905273, 135938652662043977, 6275929675565965599, 309242148569525451140, 16197470691388774460758, 898619766673014862321176, 52639402023471657682257626

Offset

0,3

Links

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

Formula

Binomial transform of A369191.

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[#]<=Length[Union@@#]&]], {n, 0, 5}]

Crossrefs

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

The covering case is A369191, for loop-graphs A369194.

The version counting all vertices is A369192.

The version for loop-graphs is A369196, counting all vertices A066383.

A006125 counts simple 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, A053530, A129271, A143543, A322661, A367916.

Sequence in context: A153558 A027335 A133686 * A396997 A369192 A385874

Adjacent sequences: A369190 A369191 A369192 * A369194 A369195 A369196

Keyword

nonn

Author

Gus Wiseman, Jan 17 2024

Status

approved