A367143 Number of simple graphs on n unlabeled vertices without isolated or universal vertices.

1, 0, 0, 0, 3, 12, 88, 732, 10258, 249976, 11455832, 994987528, 163053176864, 50171849022768, 28953151594499584, 31368377658489837792, 63938162732587949277392, 245807862122123877567929920, 1787085853417304634682510751296, 24634234097674713300981911735051072

Offset

0,5

Comments

An isolated vertex has degree 0 and a universal vertex has degree n-1.

Links

Chai Wah Wu, Table of n, a(n) for n = 0..87

Formula

a(n) = A000088(n) - 2*A000088(n-1) for n >= 2.

G.f.: x + (1 - 2*x)*B(x) where B(x) is the g.f. of A000088.

Maple

b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> `if`(n<2, 1-n, b(n$2, [])-2*b(n-1$2, [])):
seq(a(n), n=0..20);  # Alois P. Heinz, Nov 06 2023

Mathematica

b[n_, i_, l_] := If[n == 0 || i == 1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1)/2] + Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := If[n < 2, 1-n, b[n, n, {}] - 2*b[n-1, n-1, {}]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 02 2025, after Alois P. Heinz *)

Crossrefs

Cf. A000088, A002494, A367142.

Sequence in context: A266788 A039305 A174463 * A361583 A361584 A124191

Adjacent sequences: A367140 A367141 A367142 * A367144 A367145 A367146

Keyword

nonn

Author

Andrew Howroyd, Nov 06 2023

Status

approved