A367142 Number of connected simple graphs on n unlabeled vertices without universal vertices.

1, 0, 0, 0, 2, 10, 78, 697, 10073, 248734, 11441903, 994695397, 163040832612, 50170816696627, 28952985431480109, 31368326987104006472, 63938133627255371867509, 245807830666379498961633640, 1787085789384745555957516856804, 24634233851674722043622102881490796

Offset

0,5

Comments

A universal vertex is adjacent to every other vertex.

Links

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

Wikipedia, Vertex_(graph_theory).

Formula

a(n) = A001349(n) - A000088(n-1) for n > 0.

a(n) = Sum_{k=2..n-2} A332760(n,k) for n > 0.

Example

The a(4) = 2 graphs are P_4 (path graph) and C_4 (cycle graph).

Prog

(Python)
from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A367142(n):
    if n == 0: return 1
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r, s) for r, s in combinations(p.keys(), 2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items()), prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1, n))
    return sum(mobius(n//d)*c(d) for d in divisors(n, generator=True))//n-b(n-1) # Chai Wah Wu, Jul 03 2024

Crossrefs

A002494 is the not necessarily connected case.

Cf. A000088, A001349, A332760, A367143.

Sequence in context: A134980 A355471 A240599 * A212381 A098692 A300994

Adjacent sequences: A367139 A367140 A367141 * A367143 A367144 A367145

Keyword

nonn

Author

Andrew Howroyd, Nov 06 2023

Status

approved